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