Problem Description

Translated from CCC2016 Senior T5 “Circle of Life”

You may have heard of Conway's Game of Life. Conway's Game of Life runs on a grid matrix. However, it can produce very complex structures. In this problem, we will use a simplified version of the Game of Life.

This is a zero-player game. In other words, once the initial condition is given, the game runs by itself.

Divide a ring into $N$ segments, and label these $N$ segments clockwise as $1,\dots,N$. Each segment is either alive (represented by 1) or dead (represented by 0).

The game will go through $T$ rounds of “changes”. If a cell has exactly one adjacent cell that is alive during this change, then the cell will be alive in the next change. Otherwise, the cell will be dead.

Given the initial state of the ring, find the state after $T$ changes.

Input Format

The first line contains two integers $N$ and $T(3 \le N \le 100\ 000;1 \le T \le 10^{15})$.

The second line contains a string of length $N$, describing the initial states of the $N$ cells. Each character is guaranteed to be either 0 or 1. The $i$-th character represents the initial state of cell $i$.

Output Format

Output a string of length $N$, representing the final state. The format is the same as the input.

7 1
0000001

1000010

5 3
01011

10100

Hint

Sample Explanation 1

Cells $1$, $N - 1$, and $N$ are adjacent, so they remain alive after one change.

Sample Explanation 2

After one change, the state is 00011.

After two changes, the state is 10111.

For $\frac{1}{15}$ of the testdata, $N \le 15,T \le 15$.

For another $\frac{6}{15}$ of the testdata, $N \le 15$.

For another $\frac{4}{15}$ of the testdata, $N \le 4000,T \le 10\ 000\ 000$.

Note that for all testdata, you need to use 64-bit integers.

Translated by ChatGPT 5