Problem Description

Xiao Lan has a binary string $s=s_{1} s_{2} s_{3} \cdots s_{n}$.

After that, at each moment, Xiao Lan will apply a transformation to this binary string. The rule of each transformation is the same. For the binary string $s=s_{1} s_{2} s_{3} \cdots s_{n}$, the transformed binary string $s^{\prime}=s_{1}^{\prime} s_{2}^{\prime} s_{3}^{\prime} \cdots s_{n}^{\prime}$ is:

$$\begin{aligned} &s_{1}^{\prime}=s_{1} \\ &s_{i}^{\prime}=s_{i-1} \oplus s_{i} \end{aligned}$$

Here $a \oplus b$ denotes the bitwise XOR of two bits. When $a$ and $b$ are the same, the result is $0$; when $a$ and $b$ are different, the result is $1$.

What is the binary string after $t$ transformations?

Input Format

The first line contains two integers $n, t$, representing the length of the binary string and the number of transformations.

The second line contains a binary string of length $n$.

Output Format

Output one line containing a binary string, which is the transformed string.

5 3
10110

11010

Hint

Sample Explanation

Initially it is 10110. After 1 transformation it becomes 11101, after 2 transformations it becomes 10011, and after 3 transformations it becomes 11010.

Constraints

For $40\%$ of the testdata, $1 \leq n \leq 100$ and $1 \leq t \leq 1000$.

For $80\%$ of the testdata, $1 \leq n \leq 1000$ and $1 \leq t \leq 10^{9}$.

For all testdata, $1 \leq n \leq 10000$ and $1 \leq t \leq 10^{18}$.

Lanqiao Cup 2021 National Contest, Group A Problem F (Group B Problem G, Group C Problem G).

Translated by ChatGPT 5