C. 树状数组（Fenwick Tree）

时间限制：$3$ 秒 内存限制：$256$ 兆字节

定义 $\text{lowbit}(x)$ 表示整数 $x$ 在二进制下最低位 $1$ 所对应的数值。 例如：$\text{lowbit}(12)=4$，$\text{lowbit}(8)=8$。

给定长度为 $n$ 的数组 $a$，若长度为 $n$ 的数组 $s$ 对任意 $k$ 都满足：

$$s_k = \left(\sum_{i=k-\text{lowbit}(k)+1}^{k} a_i\right) \bmod 998244353 $$

则称 $s$ 是 $a$ 的树状数组，记作 $s = f(a)$。

对于正整数 $k$ 和数组 $a$，递归定义 $f^k(a)$：

$$f^k(a)= \begin{cases} f(a) & k=1\\ f\big(f^{k-1}(a)\big) & k>1 \end{cases} $$

现在给定长度为 $n$ 的数组 $b$ 和正整数 $k$，请你构造一个数组 $a$，满足： $0\le a_i < 998244353$，且 $f^k(a) = b$。

题目保证一定存在合法解，有多组解时输出任意一组即可。

输入格式

多组测试数据。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例组数。

每组测试用例： 第一行两个整数 $n,k$（$1\le n\le 2\times 10^5,\ 1\le k\le 10^9$），分别代表数组长度、迭代 $f$ 函数的次数。 第二行给出 $n$ 个整数 $b_1,b_2,\dots,b_n$（$0\le b_i<998244353$）。

保证所有测试用例的 $n$ 总和不超过 $2\times 10^5$。

输出格式

对每组测试用例，输出一行 $n$ 个整数，为任意一组合法数组 $a$。

样例输入

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]$。