Lamps

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 data

The first line of the input file LAMPS.IN contains two integers N (0 < N ≤ 10⁶) and M (0 ≤ M ≤ 10⁹). 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 data

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.

Sample