CF1967C Fenwick Tree

设 $\operatorname{lowbit}(x)$ 表示 $x$ 的二进制最低位的值，例如 $\operatorname{lowbit}(12)=4$，$\operatorname{lowbit}(8)=8$。 对于长度为 $n$ 的数组 $a$，若长度为 $n$ 的数组 $s$ 满足对于所有 $k$ 均有 $s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353$，则称 $s$ 为 $a$ 的 *树状数组* ，记为 $s=f(a)$。 对于正整数 $k$ 和数组 $a$，定义 $f^k(a)$ 如下： $$ f^k(a)= \begin{cases} f(a)&\text{若 }k=1\\ f(f^{k-1}(a))&\text{否则}\\ \end{cases} $$ 给定长度为 $n$ 的数组 $b$ 和正整数 $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$。

第一组测试数据中，可以验证 $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]$。