Baltic Olympiad in Informatics, April 23-27, 2003, Tartu, Estonia
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 file LAMPS.IN contains two integers N (0 < N ≤ 10^{6}) and M (0 ≤ M ≤ 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 file LAMPS.OUT must contain exactly N lines describing the states of the lamps after M seconds, starting with the lamp number 1.
LAMPS.IN | LAMPS.OUT |
3 1 0 0 1 |
0 1 1 |