Problem Description

Huah has $n+k$ cities numbered $1,2,.... ,n+k$, the city $i(1\le i< n+k)$ to the city $i+1$ has $n+k-i$ distinct one-way roads.

For each $x=1,2,...,n-1$,the city $i(x< i\le n+k)$ to the city $i-x$ has $a_x$ distinct one-way roads.

For $m=k+1,k+2,... ,k+n$,find the number of paths from city $k+1$ to city $m$ that pass through exactly $k$ number of roads.

Two paths are distinct when and only if the sequence of edges they pass through is distinct and the answer is modulo $998244353$.

Input

First line has one integer $T(1\le T\le 14)$, indicating there are $T$ test cases. In each case:

First line input two integers $n,k(2\le n\le 2\times 10^5,1\le k\le 2\times 10^5)$.

Second line $n-1$ integers $a_1,a_2,... ,a_{n-1}(0\le a_i\le 998244352)$.

There is a blank line between case $i(1\le i< T)$ and case $i+1$.

Input guarantee $\sum (n+k) \le 1006769$.

Output

In each case, output a row of $n$ integers with the $i$-th integer being the answer when $m=k+i$.

4
3 2
1 2
3 1
1 2
5 10
2 3 3 3
3 3
166374059 748683265

5 0 2
0 2 0
114307026 825469567 425461680 73846080 5140800
5 2 0