枚举序列

题目描述

请按字典序从小到大输出所有满足以下条件的长度为 $N$ 的整数序列。

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

什么是序列的字典序？

序列 $A = (A_1, \ldots, A_{|A|})$ 字典序小于 $B = (B_1, \ldots, B_{|B|})$，当且仅当以下 1 或 2 成立：

1. $|A| \lt |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 \lt B_i$

输入格式

输入按以下格式从标准输入给出：

$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,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}$

样例

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

数据范围

• 所有输入值均为整数。
• $1 \le N \le 8$
• $2 \le K \le 10$
• $1 \le R_i \le 5$