← 返回题目列表

Codeforces · 2072/F

F. 再见,银行家生活

中文机器翻译题面 查看原题

怪物正在逼近城市,为了保护它,明人必须在城市周围创建一个防护场。众所周知,保护领域有不同的级别。 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}$$
其中 $$$a \oplus b$$$ 是按位异“OR”(异或) 的整数 $$$a$$$ 和 $$$b$$$。

在怪物到达城市之前帮助 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$$$ 行的元素。

示例

输入
复制

5
1 5
2 10
3 16
9 1
1 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$$$。