Lamps

There are N lamps arranged in a circle. Each lamp is either on, represented by 1, or off, represented by 0.

Every second, all lamps update simultaneously. If a lamp's right neighbor was on at the previous time, that lamp toggles its own state for the next time. If its right neighbor was off, its state stays the same. The lamps are ordered from 1 to N, and lamp 1 is considered to be to the right of lamp N.

Given the initial states, determine the states of all lamps after M seconds.

The first line contains the number of lamps N and the time M. (1 ≤ N ≤ 1,000,000, 0 ≤ M ≤ 1,000,000,000)

Each of the next N lines contains the initial state of one lamp, from lamp 1 through lamp N. Each state is either 0 or 1.

Print the states after M seconds, from lamp 1 through lamp N, one per line.