Lamps

Time limit5sMemory limit128 MB

Summary

Given N lamps in a circle updating by XOR with the right neighbor each second, compute the states after M steps efficiently using binary exponentiation over XOR shifts.

Level: Medium6 of 10
Topics: Bit manipulation, Math, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples1

Example 1
Input
```
3 1
0
0
1
```
Expected output
```
0
1
1
```