C. Дерево Фенвика
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$\operatorname{lowbit}(x)$$$ обозначает значение младшего двоичного бита $$$x$$$, например, $$$\operatorname{lowbit}(12)=4$$$, $$$\operatorname{lowbit}(8)=8$$$.

Для массива $$$a$$$ длины $$$n$$$, если массив $$$s$$$ длины $$$n$$$ удовлетворяет условию $$$s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353$$$ для всех $$$k$$$, то $$$s$$$ называется Деревом Фенвика массива $$$a$$$. Обозначим его как $$$s=f(a)$$$.

Для целого положительного числа $$$k$$$ и массива $$$a$$$, $$$f^k(a)$$$ определяется следующим образом:

$$$$$$ f^k(a)= \begin{cases} f(a)&\textrm{если }k=1\\ f(f^{k-1}(a))&\textrm{иначе.}\\ \end{cases} $$$$$$

Вам дан массив $$$b$$$ длины $$$n$$$ и целое положительное число $$$k$$$. Найдите массив $$$a$$$, который удовлетворяет условию $$$0\le a_i < 998\,244\,353$$$ и $$$f^k(a)=b$$$. Можно доказать, что ответ всегда существует. Если существует несколько ответов, вы можете вывести любой из них.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых положительных числа $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) и $$$k$$$ ($$$1\le k\le 10^9$$$), обозначающих длину массива и количество раз выполнения функции $$$f$$$.

Вторая строка каждого набора входных данных содержит массив $$$b_1, b_2, \ldots, b_n$$$ ($$$0\le b_i < 998\,244\,353$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите одну строку, содержащую корректный массив $$$a$$$ длины $$$n$$$.

Пример
Входные данные
2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16
Выходные данные
1 1 1 1 1 1 1 1
1 2 3 4 5 6
Примечание

Из первого набора входных данных видно, что $$$f^1([1,1,1,1,1,1,1,1])=[1,2,1,4,1,2,1,8]$$$.

Во втором наборе входных данных видно, что $$$f^2([1,2,3,4,5,6])=f^1([1,3,3,10,5,11])=[1,4,3,17,5,16]$$$.