When talking about marsupial mammals, the first thing that comes to mind is kangaroos, followed by opossums, bandicoots, and others. Recently, Vadim discovered a new species of marsupials and named it “Prefossums.” These are very remarkable creatures; their size is comparable to young moles, with a yellow-orange coloration and white spots, a long and fluffy tail, but what impresses the most is their mathematical abilities.

If a prefossum is left with an array a of N numbers, then in just one day, the little creature will transform it into a prefix sum array p of the original array a. This means that for any position numbered i, the equation p_i = ∑ⁱ_j=1 a_j will hold. If the resulting array is not taken away from the prefossum, it will continue its actions, but with a new array.

“The world must know about this animal,” thought Vadim and set out to write a letter to IUBS, leaving an interesting array v with one prefossum. However, the process turned out to be time-consuming; it took Vadim Q days, and he just now remembered about the array he left behind. Unfortunately, the work is not yet finished, and it is essential to include the current array in the letter. Help Vadim find the values of this array.

The first line contains two integers N and Q — the number of elements in the original interesting array and the number of days the array has been with the prefossum (2 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁷).

The second line contains N integers v_i — the values of the original array (1 ≤ v_i ≤ 10⁸).

Output N integers — the values of the array after Q days with the prefossum, modulo 998 244 353.

On the first day, the prefossum will transform the original array into the array [1, 3, 6].