Description

【题意】
对于数组 $a$，有函数 $f(a)$，设数组 $s = f(a)$，则对于每一个 $s_i$，都有：$s_i = \left(\sum\limits_{j = (i \operatorname{\&} (i - 1)) + 1}^{i}{a_j}\right) \bmod 998244353$，温馨提示： $i\operatorname{\&} (i-1) = i- lowbit(i) $。

其中 $\&$ 表示按位与运算。

对于一个正整数 $k$，函数 $f^k(a)$ 定义如下：
$ f^k(a)=
\begin{cases}
    f(a)&k=1\\\\
    f(f^{k-1}(a))&k > 1 
\end{cases}$

给你正整数 $n, k$ 和一个长度为 $n$ 的数组 $b(0\le b_i < 998244353)$ 表示 $f^k(a)$，求一个符合题意的数组 $a(0 \le a_i < 998244353)$，可以证明答案总是存在的。


【输入格式】
一个整数 $ t $ ( $ 1\le t\le 10^4 $ )，表示有 $t$ 组数据。
每组数据：
第一行两个整数 $ n $ ( $ 1 \leq n \leq 2\cdot 10^5 $ ) and $ k $ ( $ 1\le k\le 10^9 $ )。
第二行 $n$ 个数 $ b_i$.
$t$ 组数据的所有 $ n $ 的总和不超过 $ 2\cdot 10^5 $ .

【输出格式】
每组数据输出一行$n$个数 $a_i$。

【样例输入】
```
4
8 1
1 2 1 4 1 2 1 8
8 2
1 3 1 8 1 3 1 20
8 3
1 4 1 13 1 4 1 38
6 2
1 4 3 17 5 16
```

【样例输出】
```
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 2 3 4 5 6
```

【提示】
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] $ .

Hint

/* 
首先我们考虑树状数组的结构。会发现a_i 最终一定只会对 a_i 以及 a_i 的祖先节点产生贡献。
那么假设有两点 i 以及 i的祖先 j，考虑 i 对  j  会贡献多少次（即节点j包含多少个a[i]）。节点j中的每个a[i]都经历了k次 f 操作。
这等价于从i开始走 k 步（每次f操作可以选择不动，或者跳到相邻的祖先节点）走到 j的路径总数，直接用插板法解决，答案为C（d+k−1，k−1）=C(d+k-1,d)。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
const LL P=998244353;
LL a[N], inv[N];
int main(){
    //freopen("a.in", "r", stdin);
    int T; scanf("%d", &T); inv[0]=inv[1]=1;
    for(int i=2; i<=N-10; i++) inv[i]=inv[P%i]*(P-P/i)%P;
    while(T--){
        int n, K; scanf("%d%d", &n, &K);
        for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
        for(int i=1; i<=n; i++){
            LL t=1;
            for(LL j=i+i&-i, d=1; j<=n; j+=j&-j, d++){
                t=t*(d+K-1)%P*inv[d]%P;
                a[j]=(a[j]-t*a[i]%P+P)%P;
            }
        }
        for(int i=1; i<=n; i++) printf("%lld ", a[i]); printf("\n");
    }
return 0;

}

</p>