Today is a morning of the 1st day and you have N boxes in a line. The ith box from left has Ai 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 Mth 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 A1,A2,..,AN 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 Mth day.
Constraints
1≤T≤10001≤N≤5×1051≤M≤10181≤Ai<998244353Sum of N over all test cases does not exceed 2×106
In the first test case, we have N=3, A=[2,3,5]. We need to report chocolates on morning of 3rd 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 3rd morning.
In the second test case, we have N=2, A=[2,4]. Clearly on the morning of Mth day, we would have 2+4×(M−1) chocolates in the first box and 4 chocolates in second box. Therefore array becomes [2+4×838289191,4]. Since we need to take mod 998244353, we output the array [358423707,4].
