Problem Description

Output all integer sequences of length $ N $ that satisfy the following conditions in lexicographical order:

• The $ i $th element is between $ 1 $ and $ R_i $ inclusive.
• The sum of the elements is a multiple of $ K $.

What is lexicographical order? A sequence $A = (A_1, \ldots, A_{|A|})$ is strictly lexicographically smaller than $B = (B_1, \ldots, B_{|B|})$ if either 1. or 2. below holds:
1. $ |A| < |B| $ and $(A_1, \ldots, A_{|A|}) = (B_1, \ldots, B_{|A|})$.
2. There exists an integer $1 \leq i \leq \min\{|A|, |B|\}$ such that both of the following are true:
- $(A_1, \ldots, A_{i-1}) = (B_1, \ldots, B_{i-1})$
- $ A_i < B_i $

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ R_1 $ $ R_2 $ $\dots$ $ R_N $

Output Format

When there are $ X $ sequences to output, and the $ i $th sequence is $A_i = (A_{i,1}, A_{i,2}, \dots, A_{i,N})$, output the answer in the following format:

$ A_{1,1} $ $ A_{1,2} $ $\dots$ $ A_{1,N} $ $ A_{2,1} $ $ A_{2,2} $ $\dots$ $ A_{2,N} $ $\vdots$ $ A_{X,1} $ $ A_{X,2} $ $\dots$ $ A_{X,N} $

Sample Input and Output

Sample Input #1

3 2
2 1 3

Sample Output #1

1 1 2
2 1 1
2 1 3

Sample Input #2

1 2
1

Sample Output #2

Sample Input #3

5 5
2 3 2 3 2

Sample Output #3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1

Notes/Hints

Constraints

• All inputs are integers.
• $1 \le N \le 8$
• $2 \le K \le 10$
• $1 \le R_i \le 5$

Sample Explanation 1

The sequences to output are $ 3 $ in total, and they are $ (1,1,2), (2,1,1), (2,1,3) $ in lexicographical order.

Sample Explanation 2

There may be no sequences to output. In this case, the output should be empty.

见题面 Input 部分

见题面 Output 部分