Blink

Unhappy with the dim lighting in his barn, Farmer John has installed a fancy new chandelier made of $N$ ($3 \le N \le 16$) light bulbs arranged in a circle.

The cows are fascinated by the new fixture and enjoy the following game. At each time step $T$, a bulb toggles its state (on↔off) if and only if its left neighbor was on at time $T-1$. The bulbs form a circle, so the left neighbor of bulb $1$ is bulb $N$. The cows repeat this for $B$ ($1 \le B \le 10^{15}$) time steps. Note that $B$ may exceed the range of a 32-bit integer.

Given the initial states of the bulbs, determine their states after exactly $B$ time steps.

• Line $1$: two space-separated integers $N$ and $B$.
• Lines $2 \dots N+1$: line $i+1$ contains the initial state of bulb $i$ — $0$ (off) or $1$ (on).

• Lines $1 \dots N$: line $i$ contains the final state of bulb $i$ after $B$ time steps — $0$ (off) or $1$ (on).

With $N = 5$ bulbs where only the first is initially on (1 0 0 0 0), the states evolve as follows:

So after $B = 6$ steps the bulbs read 1 1 1 0 1.