F. Goodbye, Banker Life
2-sat; bitmasks; combinatorics; constructive algorithms; fft; math; number theory
Monsters are approaching the city, and to protect it, Akito must create a protective field around the city. As everyone knows, protective fields come in various levels. Akito has chosen the field of level \(n\). To construct the field, a special phrase is required, which is the \(n\)-th row of the Great Magical Triangle, represented as a two-dimensional array. We will call this array \(T\).The triangle is defined as follows: In the \(i\)-th row, there are \(i\) integers. The single integer in the first row is \(k\). Let the \(j\)-th element of the \(i\)-th row be denoted as \(T_{i,j}\). Then $$$\(T_{i,j} = \begin{cases} T_{i-1,j-1} \oplus T_{i-1,j}, &\textrm{if } 1 < j < i \\ T_{i-1,j}, &\textrm{if } j = 1 \\ T_{i-1,j-1}, &\textrm{if } j = i \end{cases}\)\( where \)a \oplus b\( is the bitwise exclusive ""OR""(XOR) of the integers \)a\( and \)b\(.Help Akito find the integers in the \)n$$$-th row of the infinite triangle before the monsters reach the city.
The first line contains the integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases.In the only line of each test case, there are two integers \(n\) and \(k\) (\(1 \le n \le 10^6,\ 1 \le k < 2^{31}\)) — the row index that Akito needs and the integer in the first row of the Great Magical Triangle, respectively.It is guaranteed that the sum of \(n\) across all test cases does not exceed \(10^6\).
For each test case, output \(n\) integers — the elements of the \(n\)-th row of the Great Magical Triangle.
In the first example, the first row of the Great Magical Triangle is \([5]\) by definition.In the second example, \(T_{2,1} = T_{1,1} = 10\) and \(T_{2,2} = T_{1, 1} = 10\).