怪物正在逼近城市,为了保护它,明人必须在城市周围创建一个防护场。众所周知,保护领域有不同的级别。 Akito 选择了 $$$n$$$ 级别的领域。为了构造这个字段,需要一个特殊的短语,它是神奇大三角的第 $$$n$$$ 行,表示为二维数组。我们将这个数组称为$$$T$$$。
三角形定义如下:
- 在第 $$$i$$$ 行中,有 $$$i$$$ 个整数。
- 第一行中的单个整数是 $$$k$$$。
- 令第 $$$i$$$ 行的第 $$$j$$$ 元素表示为 $$$T_{i,j}$$$。然后 $$T_{i,j} = \begin{cases} T_{i-1,j-1} \oplus T_{i-1,j}, &\textrm{if } 1 \lt j \lt i \\ T_{i-1,j}, &\textrm{if } j = 1 \\ T_{i-1,j-1}, &\textrm{if } j = i \end{cases}$$
在怪物到达城市之前帮助 Akito 找到无限三角形的第 $$$n$$$ 行中的整数。
输入
第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
在每个测试用例的唯一行中,有两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^6,\ 1 \le k \lt 2^{31}$$$)——分别是 Akito 需要的行索引和大魔法三角第一行的整数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个整数 — 大魔法三角形第 $$$n$$$ 行的元素。
示例
输入复制
51 52 103 169 11 52
输出复制
5 10 10 16 0 16 1 0 0 0 0 0 0 0 1 52
注意
在第一个示例中,根据定义,神奇大三角的第一行是 $$$[5]$$$。
在第二个示例中,$$$T_{2,1} = T_{1,1} = 10$$$ 且 $$$T_{2,2} = T_{1, 1} = 10$$$。