题目描述

强哥是一位魔法宝石收藏家，他最近发现了一组神奇的宝石，每颗宝石都有一个魔力值。强哥为每颗宝石设定了一个魔力值上限 $(r_1, r_2, \ldots, r_n)$，表示每颗宝石的魔力值不能超过这个上限。此外，他还发现了一个“魔法倍数” $k$，只有当所有宝石的魔力值之和是 $k$ 的倍数时，这些宝石才能组合成一个强大的魔法阵。

强哥希望你能帮助他找到所有满足以下条件的宝石组合 $(a_1, a_2, \ldots, a_n)$：

1. $1 \leq a_i \leq r_i$（每颗宝石的魔力值不能超过上限）；
2. $a_1 + a_2 + \cdots + a_n$ 是 $k$ 的倍数。

更重要的是，这些组合必须按照字典序从小到大的顺序列出来，否则强哥会不满意！

输入格式

第一行输入两个整数 $n$ 和 $k$，分别表示宝石的数量和魔法倍数。 第二行输入 $n$ 个整数 $r_1, r_2, \ldots, r_n$，表示每颗宝石的魔力值上限。

输出格式

输出若干行，每行一个满足条件的宝石组合，按照字典序从小到大排列。

样例输入

3 2
2 1 3

样例输出

1 1 2
2 1 1
2 1 3

数据范围

• $n \leq 8$；
• $1 \leq r_i \leq 5$；
• $2 \leq k \leq 10$。