Fenwick Tree
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 2300
Tags: bitmasks, brute force, combinatorics, data structures, dp, math, trees

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 format:
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 format:
For each test case, print a single line, containing a valid array $$$a$$$ of length $$$n$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16

Example output:
1 1 1 1 1 1 1 1
1 2 3 4 5 6

Editorial:
It's well-known that Fenwick Tree is the data structure shown in the image below, and the sum of each subtree is stored at each vertex (i.e. $$$c=f(a)$$$ and $$$c_u=\sum\limits_{v\textrm{ in subtree of }u}a_v$$$).

Denote the depth of a vertex $$$u$$$ as $$$\operatorname{dep}(u)$$$. Assume that $$$b=f^k(a)$$$. Consider a vertex $$$u$$$ and one of its ancestors $$$v$$$. Let $$$\Delta d=\operatorname{dep}(u)-\operatorname{dep}(v)$$$. It can be easily proved (by using the stars and bars method or generating functions) that the coefficient of $$$a_u$$$ in $$$b_v$$$ is $$$\binom{\Delta d+k-1}{\Delta d}$$$.
Obviously, $$$a_u=b_u$$$ is satisfied for each leaf $$$u$$$. Enumerate each vertex $$$u$$$ whose $$$a$$$ value is already known (just in the increasing order is fine), and all its ancestors $$$v$$$, remove the $$$\textrm{coefficient}\cdot a_u$$$ part from $$$b_v$$$, and we can calculate the $$$a$$$ value of each vertex.
Time complexity is $$$\mathcal O(n\log n)$$$ because the height of a Fenwick Tree is $$$\mathcal O(\log n)$$$.