311296: CF1967C. Fenwick Tree

C. Fenwick Treetime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Let $\operatorname{lowbit}(x)$ denote the value of the lowest binary bit of $x$, e.g. $\operatorname{lowbit}(12)=4$, $\operatorname{lowbit}(8)=8$.

For an array $a$ of length $n$, if an array $s$ of length $n$ satisfies $s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353$ for all $k$, then $s$ is called the Fenwick Tree of $a$. Let's denote it as $s=f(a)$.

For a positive integer $k$ and an array $a$, $f^k(a)$ is defined as follows:

$$ f^k(a)= \begin{cases} f(a)&\textrm{if }k=1\\ f(f^{k-1}(a))&\textrm{otherwise.}\\ \end{cases} $$

You are given an array $b$ of length $n$ and a positive integer $k$. Find an array $a$ that satisfies $0\le a_i < 998\,244\,353$ and $f^k(a)=b$. It can be proved that an answer always exists. If there are multiple possible answers, you may print any of them.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains two positive integers $n$ ($1 \leq n \leq 2\cdot 10^5$) and $k$ ($1\le k\le 10^9$), representing the length of the array and the number of times the function $f$ is performed.

The second line of each test case contains an array $b_1, b_2, \ldots, b_n$ ($0\le b_i < 998\,244\,353$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, print a single line, containing a valid array $a$ of length $n$.

ExampleInput

2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16

Output

1 1 1 1 1 1 1 1
1 2 3 4 5 6

Note

In the first test case, it can be seen that $f^1([1,1,1,1,1,1,1,1])=[1,2,1,4,1,2,1,8]$.

In the second test case, it can be seen that $f^2([1,2,3,4,5,6])=f^1([1,3,3,10,5,11])=[1,4,3,17,5,16]$.

题目大意：
这个题目是关于Fenwick Tree（树状数组）的。给定一个数组a，可以通过一个函数f得到它的Fenwick Tree s。函数f的定义是，对于数组a中的每个元素s[k]，它是a中从k - lowbit(k) + 1到k的元素之和模998,244,353的结果。这里的lowbit(x)表示x最低位的二进制位。例如，lowbit(12)=4，lowbit(8)=8。

题目还定义了f的k次方，即f^k(a)。如果k=1，那么f^k(a)就是f(a)；如果k大于1，那么f^k(a)就是f(f^(k-1)(a))。

题目要求给定一个数组b和一个正整数k，找到一个数组a，使得f^k(a)=b，并且a中的每个元素满足0≤a_i<998,244,353。题目保证至少存在一个这样的数组a。

输入输出数据格式：
输入：
- 第一行包含一个正整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个正整数n（1≤n≤2×10^5）和k（1≤k≤10^9），分别表示数组a的长度和函数f执行的次数。
- 每个测试用例的第二行包含n个整数b_1, b_2, ..., b_n（0≤b_i<998,244,353），表示数组b的元素。
- 保证所有测试用例的n之和不超过2×10^5。

输出：
- 对于每个测试用例，输出一行，包含一个长度为n的数组a。题目大意： 这个题目是关于Fenwick Tree（树状数组）的。给定一个数组a，可以通过一个函数f得到它的Fenwick Tree s。函数f的定义是，对于数组a中的每个元素s[k]，它是a中从k - lowbit(k) + 1到k的元素之和模998,244,353的结果。这里的lowbit(x)表示x最低位的二进制位。例如，lowbit(12)=4，lowbit(8)=8。 题目还定义了f的k次方，即f^k(a)。如果k=1，那么f^k(a)就是f(a)；如果k大于1，那么f^k(a)就是f(f^(k-1)(a))。 题目要求给定一个数组b和一个正整数k，找到一个数组a，使得f^k(a)=b，并且a中的每个元素满足0≤a_i<998,244,353。题目保证至少存在一个这样的数组a。 输入输出数据格式： 输入： - 第一行包含一个正整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含两个正整数n（1≤n≤2×10^5）和k（1≤k≤10^9），分别表示数组a的长度和函数f执行的次数。 - 每个测试用例的第二行包含n个整数b_1, b_2, ..., b_n（0≤b_i<998,244,353），表示数组b的元素。 - 保证所有测试用例的n之和不超过2×10^5。 输出： - 对于每个测试用例，输出一行，包含一个长度为n的数组a。