Problem Description

Translated from CCC2016 Senior T5「Circle of Life」

Perhaps you have heard of Conway's Game of Life. It operates on a matrix composed of grids, yet it can generate extremely complex structures. In this problem, we will use a simplified version of the Game of Life to challenge you.

This game is a zero-player game, meaning that once the initial conditions are set, the game can proceed on its own.

A circle is divided into $N$ segments, which are numbered clockwise as $1, \dots, N$. Each segment is either alive (represented by 1) or dead (represented by 0).

The game will undergo $T$ rounds of "changes". If a segment has exactly one neighboring segment that survives during this change, then that segment will survive in the next change. Otherwise, the segment will die.

Given the initial state of the circle, 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$, representing the initial state of the $N$ segments. Each character is either 0 or 1. The $i$-th character represents the initial state of the segment numbered $i$.

Output Format

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

Sample Input and Output

Sample Input #1

7 1
0000001

Sample Output #1

1000010

Sample Input #2

5 3
01011

Sample Output #2

10100

Notes/Hints

Sample Explanation 1

Segments $1$ and $N - 1$ and $N$ are adjacent, so they survive 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 data, $N \le 15, T \le 15$.

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

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

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

见题面 Input 部分

见题面 Output 部分