P15514 [BalticOI 2003] Lamps (Day 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.

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.

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