题目描述

请把所有满足下列条件的、由非负整数组成的长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ 按字典序从小到大全部输出：

保证输入满足条件的序列个数不超过 $3 \times 10^5$ 个。

什么是序列的字典序？

称序列 $S = (S_1, S_2, \ldots, S_{|S|})$ 字典序小于序列 $T = (T_1, T_2, \ldots, T_{|T|})$，是指下面 1. 与 2. 中至少有一条成立（其中 $|S|, |T|$ 分别表示 $S, T$ 的长度）：

1. $|S| < |T|$ 且 $(S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|})$；
2. 存在整数 $1 \le i \le \min\{|S|, |T|\}$，使得下面两条同时成立：
   • $(S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})$
   • $S_i$ 作为数值小于 $T_i$。

输入格式

N K

输出格式

设满足条件的非负整数序列有 $q$ 个，输出 $q$ 行。每行按顺序输出一个序列的各个元素，元素之间用一个空格隔开。

对任意一个序列，排在它前面输出的所有序列都必须字典序比它小。

输入示例 1

3 8

输出示例 1

0 1 2
0 4 0
1 2 1
2 0 2
2 3 0
3 1 1
4 2 0
5 0 1
6 1 0
8 0 0

示例 1 说明

例如序列 $(0,1,2)$ 满足 $0 \times 1 + 1 \times 2 + 2 \times 3 = 0 + 2 + 6 = 8$，符合条件。不存在字典序比它更小的合法序列，所以第 $1$ 行输出 0 1 2。

连同 $(0,1,2)$ 在内共有 $10$ 个序列满足条件，按字典序从小到大依次输出。

输入示例 2

1 200000

输出示例 2

200000

示例 2 说明

$N = 1$ 时式子变成 $1 \times A_1 = K$，解唯一。这组数据用来检验 $K$ 取到上限时的输出，以及只有一个元素时行末不应有多余空格。

输入示例 3

8 9

输出示例 3

0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 3 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 1 1 0 0 0 0
0 2 0 0 1 0 0 0
0 3 1 0 0 0 0 0
1 0 0 0 0 0 0 1
1 0 0 2 0 0 0 0
1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 2 0 0 0 0 0
1 2 0 1 0 0 0 0
1 4 0 0 0 0 0 0
2 0 0 0 0 0 1 0
2 0 1 1 0 0 0 0
2 1 0 0 1 0 0 0
2 2 1 0 0 0 0 0
3 0 0 0 0 1 0 0
3 0 2 0 0 0 0 0
3 1 0 1 0 0 0 0
3 3 0 0 0 0 0 0
4 0 0 0 1 0 0 0
4 1 1 0 0 0 0 0
5 0 0 1 0 0 0 0
5 2 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 1 0 0 0 0 0 0
9 0 0 0 0 0 0 0

示例 3 说明

$N = 8$ 而 $K = 9$ 较小，此时很多下标的系数（如 $i = 8$）已经接近 $K$，大量分支走不通。这组数据用来检验可行性剪枝是否正确：注意第 $1$ 行是 $(0,0,0,1,1,0,0,0)$ 而不是 $(0,0,0,0,\ldots)$，因为 $A_1 = A_2 = A_3 = 0$ 之后剩下的 $9$ 必须能用系数 $4 \sim 8$ 凑出来，$9 = 4 + 5$ 是字典序最小的凑法。

约束条件

• $1 \le N \le 10$
• $1 \le K \le 2 \times 10^5$
• 满足条件的序列个数不超过 $3 \times 10^5$ 个
• 所有输入值均为整数