F. Прощай, жизнь банкира, здравствуй, жизнь мага
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На город надвигаются монстры, и для защиты от них Акито должен создать защитное поле вокруг города. Защитные поля, как всем известно, бывают различных уровней. Акито выбрал поле $$$n$$$-го уровня. Чтобы возвести поле, необходима особая фраза, которая является $$$n$$$-й строчкой Великого Магического Треугольника, представимого в виде двумерного массива. Назовем этот массив $$$T$$$.

Треугольник задается следующим образом:

  • В $$$i$$$-й строке $$$i$$$ чисел.
  • Единственное число в первой строке — $$$k$$$.
  • Пусть $$$j$$$-й элемент $$$i$$$-й строки обозначается как $$$T_{i,j}$$$. Тогда $$$$$$T_{i,j} = \begin{cases} T_{i-1,j-1} \oplus T_{i-1,j}, &\textrm{если } 1 < j < i \\ T_{i-1,j}, &\textrm{если } j = 1 \\ T_{i-1,j-1}, &\textrm{если } j = i \end{cases}$$$$$$
где $$$a \oplus b$$$ — побитовое исключающее «ИЛИ»(XOR) чисел $$$a$$$ и $$$b$$$.

Помогите Акито, найдите числа в $$$n$$$-й строке бесконечного треугольника, пока монстры не добрались до города.

Входные данные

В первой строке дано число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В единственной строке каждого набора данных даны два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^6,\ 1 \le k < 2^{31}$$$) — номер строки, которая необходима Акито, и число в первой строке Великого Магического Треугольника соответственно.

Гарантируется, что сумма $$$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$$$.