题目描述

有一个无限的“魔法三角形” $T$。给定第一行唯一的数 $k$，三角形按下面的规则生成：

• 第 $i$ 行有 $i$ 个整数。
• 第一行只有一个整数 $k$。
• 对于 $i>1$，第 $i$ 行第 $j$ 个数 $T_{i,j}$ 满足：

$$T_{i,j} = \begin{cases} T_{i-1,j-1} \oplus T_{i-1,j}, & 1 < j < i,\\ T_{i-1,j}, & j = 1,\\ T_{i-1,j-1}, & j = i. \end{cases}$$

其中 $\oplus$ 表示按位异或。

现在给出若干组询问，每组给定 $n$ 和 $k$，请输出这个三角形的第 $n$ 行。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

接下来 $t$ 行，每行包含两个整数 $n,k$，表示需要输出第 $n$ 行，且第一行的数为 $k$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数，表示第 $n$ 行从左到右的所有元素。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 10^6$
• $1 \le k < 2^{31}$
• 所有测试用例的 $n$ 之和不超过 $10^6$

样例输入

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

样例解释

第一组中，第 $1$ 行按定义就是 $[5]$。

第二组中，第二行两个端点都从上一行复制得到，所以答案为 10 10。