After a long year of preparing presents for all of the little children of the world, Santa's elves are ready to go on their annual cottage vacation in Santa's private luxury winter retreat!

Santa's winter retreat consists of $N$ cottages numbered from $1$ to $N$. In addition, the cottages are arranged in a circular fashion with the $(i+1)$-th cottage being adjacent to the $i$-th one for all $1\le i\le N-1$ and the first cottage being adjacent to the $N$-th one.

Initially, the $i$-th cottage has exactly $a_i$ elves in it. Since the elves want to check out the new features installed in the cottages, they will follow the following procedure for each of the next $K$ hours of their stay:

• Simultaneously, exactly $1$ elf from each cottage will move to the next cottage in the circle if and only if the cottage has a positive number of elves. Note that elves from cottage $N$ would move to cottage $1$.

After repeating this procedure exactly $K$ times, please report to Santa how many elves are in each cottage!

Constraints

$1\le N\le {10}^6$

$0\le K\le {10}^9$

$0\le a_i\le {10}^9$

Input Specification

The first line contains two space-separated integers $N$ and $K$, denoting the number of cottages and hours respectively.

The second line contains $N$ space-separated integers $a_1,a_2,\dots ,a_N$, the initial number of elves in each cottage.

Output Specification

Output $N$ space-separated integers, the $i$-th being the number of elves after $K$ hours at the $i$-th cottage.

Sample Input

5 3
1 0 0 1 0

Sample Output

0 1 0 1 0