树状数组逆变换

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

定义 $\operatorname{lowbit}(x)$ 为 $x$ 的二进制最低位所代表的数，例如 $\operatorname{lowbit}(12)=4$。

对长度为 $n$ 的数组 $a$，定义变换 $f$：

$$f(a)_i=\left(\sum_{j=i-\operatorname{lowbit}(i)+1}^{i}a_j\right)\bmod 998244353.$$

记 $f^k$ 为连续执行 $k$ 次变换 $f$。给定数组 $b$ 和正整数 $k$，请构造数组 $a$，使得 $f^k(a)=b$，并满足 $0\le a_i<998244353$。

可以证明答案一定存在。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例第一行包含两个整数 $n,k$。第二行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

对每个测试用例输出一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示任意一个合法答案。

样例输入 1

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
1 2 3 4 5 6

数据范围

• $1\le t\le10^4$；
• $1\le n\le2\cdot10^5$，$1\le k\le10^9$；
• $0\le b_i<998244353$；
• 所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

本题采用独立测试点计分。

子任务编号	分值	特殊限制
1	20	$n\le20$，$k\le20$，且单个输入文件中 $\sum n\le200$
2	40	$n\le45$，且单个输入文件中 $\sum n\le450$
3		无特殊限制