问题描述

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

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

（如果你已经知道字典序的含义，以下可忽略：）

什么是序列的字典顺序？序列 $A=(A_1,\ldots,A_{|A|})$ 在字典序上小于 $B=(B_1,\ldots,B_{|B|})$，如果下面的两条之一成立：

• $|A|<|B|$ 且 $(A_{1},\ldots,A_{|A|})=(B_1,\ldots,B_{|A|})$。
• 存在整数 $1≤i≤\min\{|A|,|B|\}$，使得以下两个条件均为真:$(a_{1},\ldots,a_{i-1})=(B_1,\ldots,B_{i-1})$ 且 $A_i<B_i$。

数据规模

所有输入值都是整数。

$1≤N≤8$

$2≤K≤10$

$1≤R_i≤5$

输入

输入来自标准输入，格式如下:

$N\ K$

$R_1\ R_2\ \dots\ R_N$

输出

按以下格式打印答案，其中 $X$ 是要打印的序列数，第 $i$ 个序列是 $A_i=(A_{i,1},A_{i,2},\dots,A_{i,N})$：

$A_{1,1}\ A_{1,1}\ \dots \ A_{1,N}$

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

$\dots$

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

3 2
2 1 3

1 1 2
2 1 1
2 1 3

要打印的序列有三个，按字典顺序分别是 $(1,1,2)$，$(2,1,1)$，$(2,1,3)$。

1 2
1

可能没有要打印的序列。在这种情况下，输出可以为空。

5 5
2 3 2 3 2

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