Circle of Life

Conway's Game of Life applies a handful of rules to cells on a grid and still produces very complicated configurations. This problem uses a version of that game simplified down to a one dimensional circular strip.

There is a circular strip of $N$ cells. The cells are numbered from 1 to $N$ in order: cell 1 and cell 2 are adjacent, cell 2 and cell 3 are adjacent, and so on up to cell $N-1$, which is adjacent to cell $N$. Since the strip is circular, cell 1 is also adjacent to cell $N$.

Each cell is either alive or dead. An alive cell is written as the character '1' and a dead cell as the character '0'. When a generation passes, every cell changes state at the same time. If exactly one of a cell's two neighbours is alive in the current generation, then the cell is alive in the next generation. Otherwise the cell is dead in the next generation.

Given the initial state of the strip, find the state after $T$ generations.

The first line contains two integers $N$ and $T$ separated by a space ($3 \le N \le 100000$, $1 \le T \le 10^{15}$).

The second line contains a string of exactly $N$ characters describing the initial state. Each character is either '0' or '1', and the $i$-th character is the initial state of cell $i$. The character '1' means an alive cell and '0' means a dead cell.

Print the state of the $N$ cells after $T$ generations on one line, in the same format and order as the input. That is, print a string of $N$ characters whose $i$-th character is '1' if cell $i$ is alive and '0' if it is dead.