Score : $300$ points

问题陈述

以升序的字典序打印所有长度为 $N$ 的整数序列，满足以下条件：

• 第 $i$ 个元素在 $1$ 到 $R_i$（包括 $1$ 和 $R_i$）之间。
• 所有元素的和是 $K$ 的倍数。

什么是序列的字典序？如果满足以下条件之一，则序列 $A = (A_1, \ldots, A_{|A|})$ 字典序小于 序列 $B = (B_1, \ldots, B_{|B|})$：

1. $|A|<|B|$ 且 $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$。
2. 存在一个整数 $1\leq i\leq \min\{|A|,|B|\}$ 使得以下两个条件同时成立：
   • $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$
   • $A_i < B_i$

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

Print all integer sequences of length $N$ that satisfy the following conditions, in ascending lexicographical order.

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

What is lexicographical order for sequences? A sequence $A = (A_1, \ldots, A_{|A|})$ is 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$

Constraints

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

Input

The input is given from Standard Input in the following format:

$N$ $K$

$R_1$ $R_2$ $\dots$ $R_N$

Output

Print the answer in the following format, where $X$ is the number of sequences to print, the $i$-th of which is $A_i=(A_{i,1},A_{i,2},\dots,A_{i,N})$:

$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 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are $(1,1,2),(2,1,1),(2,1,3)$ in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

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

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