Baltic Olympiad in Informatics: 2003 Day 2, Problem 2

There is a castle with a circular main hall. There are $N$ lamps numbered from $1$ to $N$ on the wall of the hall. Each of the lamps can be either on or off. At each second the lamp number $i$ changes its state if the lamp number $i+1$ is on, except the lamp number $N$ changes its state if the lamp number $1$ is on.

Your task is, given the initial states of all lamps at some moment, to find their states after $M$ seconds.

Input Specification

The first line of the input contains two integers $N$ $(0<N\le {10}^6)$ and $M$ $(0\le M\le {10}^9)$. The next $N$ lines contain the initial states of the lamps, starting with the lamp number $1$. A line containing $0$ means that the lamp is off and $1$ means that the lamp is on.

Output Specification

The output must contain exactly $N$ lines describing the states of the lamps after $M$ seconds, starting with the lamp number $1$.

Sample Input

3 1
0
0
1

Sample Output

0
1
1