Given an array a₀ of size n (1 < n < 10⁵). Find the array a_k modulo (7340033)

where a_k = cumulative summation array of the array a_k-1.

Means,

                        a_k[1] = a_k-1[1]

for i > 1 , a_k[i] = a_k[i-1] + a_k-1[i]

Given k (0 < k < 10⁵)

Can you find the array a_k efficiently?

For example,

If  a₀ = {1, 2, 1, 3},

    a₁  = {1, 3, 4, 7}

    a₂ = {1, 4, 8, 15}

    a₃ = {1, 5, 13, 28}  

Input

First line will contain two integer n, k (size of the array and k from the problem description)

Following n positive integers separated by spaces denoting array a₀ .

All integers are smaller than 10⁵.

Output

Output n integers of the array a_k with spaces in between.

Example

Input:
4 2
1 2 1 3
Output:
1 4 8 15