题目描述

给定长度为 $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 \le 8$，$1 \le r_i \le 5$，$2 \le k \le 10$。

样例 1

输入

3 2
2 1 3

输出

1 1 2
2 1 1
2 1 3

样例 2

输入

1 2
1

输出

样例 3

输入

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