该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定长度为 $n$ 的正整数序列 $(r_1, \ldots, r_n)$ 和正整数 $k$。

以字典序从小到大的顺序输出所有满足 $1 \le a_i \le r_i$ 且 $a_1 + \cdots + a_n$ 是 $k$ 的倍数的长度为 $n$ 的整数序列 $(a_1, \ldots, a_n)$。

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

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

数列的字典序

​ 数列$A = (A_1, \ldots, A_{|A|})$在字典序上严格小于数列$B = (B_1, \ldots, B_{|B|})$，是指满足以下1. 或2. 中的任意一条。

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$

输入格式

第一行两个整数 $n, k$，第二行 $n$ 个整数 $r_1, \ldots, r_n$。

输出格式

若干行，每行一个满足条件的序列 $a$，以字典序从小到大的顺序输出。

样例 #1

样例输入 #1

3 2
2 1 3

样例输出 #1

1 1 2
2 1 1
2 1 3

样例 #2

样例输入 #2

1 2
1

样例输出 #2

样例 #3

样例输入 #3

5 5
2 3 2 3 2

样例输出 #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

数据范围

• $1\ \le\ N\ \le\ 8$
• $2\ \le\ K\ \le\ 10$
• $1\ \le\ R_i\ \le\ 5$

样例1解释

应输出的序列有3个 ，分别是 $(1,1,2),(2,1,1),(2,1,3)$ 。

样例2解释

也有可能不存在应输出的数列。在这种情况下，输出为空。