题目描述

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

你需要生成一个长度为 $n$ 的序列 $a$，对于所有的 $i\ (1\leq i\leq n)$ 满足 $1\leq a_i\leq r_i$。且 $k\mid \sum\limits_{i=1}^n a_i$。

其中 $\sum\limits_{i=1}^n a_i$ 代表 $a_1+a_2+\cdots+a_n$，$|$ 为整除符号。即 $k$ 整除 $a_i$ 的总和。

按照字典序从小到大的顺序输出所有序列

输入格式

第一行两个整数 $n, k$

第二行 $n$ 个整数 $r_1, \ldots, r_n$。

输出格式

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

3 2
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

提示

数据范围

• $n \le 8$，$1 \le r_i \le 5$，$2 \le k \le 10$。