Today is a morning of the $$1^{st}$$ day and you have $$N$$ boxes in a line. The $$i^{th}$$ box from left has $$A_i$$ chocolates. Every night, the number of chocolates in each box increases by an amount equal to the total number of chocolates that were present in the morning in the boxes to the right of it.
You need to print the number of chocolates in each box on the morning of $$M^{th}$$ day.
The number of chocolates can be very huge, you need to output it modulo $$998244353$$. You can read about modular arithmetic here.
You are given $$T$$ test cases.
Input format
- The first line contains a single integer $$T$$ denoting the number of test cases.
- The first line of each test case contains two space-separated integers $$N$$ and $$M$$ denoting the number of boxes and the day on which you need to report the chocolates.
- The second line of each test case contains $$N$$ space-separated integers $$A_1, A_2,..,A_N$$ denoting the number of chocolates in each box. Note that $$1$$ is the leftmost box.
Output format
For each test case(in a separate line), output $$N$$ space-separated integers in a single line denoting the number of chocolates in each box on the morning of $$M^{th}$$ day.
Constraints
$$ 1 \le T \le 1000 \\
1 \le N \le 5 \times 10^5 \\
1 \le M \le 10^{18} \\
1 \le A_i < 998244353 \\
\text{Sum of N over all test cases does not exceed } 2 \times 10^6 $$
In the first test case, we have $$N = 3$$, $$A = [2, 3, 5]$$. We need to report chocolates on morning of $$3^{rd}$$ day.
On the first night, the array becomes $$[2 + 3 + 5, 3 + 5, 5] = [10, 8, 5]$$, that is chocolates in a particular box increases by amount equal to total number of chocolates that were present in the boxes to the right of it.
On second night, the array becomes $$[10 + 8 + 5, 8 + 5, 5] = [23, 13, 5]$$. This would be the required number of chocolates on $$3^{rd}$$ morning.
In the second test case, we have $$N = 2$$, $$A = [2, 4]$$. Clearly on the morning of $$M^{th}$$ day, we would have $$2 + 4 \times (M - 1)$$ chocolates in the first box and $$4$$ chocolates in second box. Therefore array becomes $$[2 + 4 \times 838289191, 4]$$. Since we need to take mod $$998244353$$, we output the array $$[358423707, 4]$$.
