311349: CF1972E. Fenwick Tree

E. 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树（也称为二叉索引树）的。给定一个数组a，其Fenwick树s可以通过数组a计算得到，计算方式是s[k]等于a中从k-lowbit(k)+1到k的元素之和模上998,244,353。定义f(a)为a的Fenwick树。另外，定义f^k(a)为对a连续进行k次f操作的结果。题目要求给定一个数组b和一个正整数k，找到一个数组a，使得f^k(a)=b，并且a中的元素满足0≤a[i]<998,244,353。题目保证至少存在一个解。

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

输出：
- 对于每个测试用例，输出一行，包含一个长度为n的数组a，满足f^k(a)=b。

示例：
输入：
```
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]。题目大意： 这个题目是关于Fenwick树（也称为二叉索引树）的。给定一个数组a，其Fenwick树s可以通过数组a计算得到，计算方式是s[k]等于a中从k-lowbit(k)+1到k的元素之和模上998,244,353。定义f(a)为a的Fenwick树。另外，定义f^k(a)为对a连续进行k次f操作的结果。题目要求给定一个数组b和一个正整数k，找到一个数组a，使得f^k(a)=b，并且a中的元素满足0≤a[i]<998,244,353。题目保证至少存在一个解。 输入输出数据格式： 输入： - 第一行包含一个正整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个正整数n和k（1≤n≤2×10^5，1≤k≤10^9），分别表示数组长度和函数f执行的次数。 - 第二行包含n个整数b_1, b_2, ..., b_n（0≤b_i<998,244,353），表示数组b的元素。 - 所有测试用例的n之和不超过2×10^5。 输出： - 对于每个测试用例，输出一行，包含一个长度为n的数组a，满足f^k(a)=b。 示例： 输入： ``` 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]。