Person in Charge

• 035966_L3

Attention

This problem requires file I/O (lottery.in / lottery.out).

In this problem, the indices of binary strings start from $\bm{0}$ (leftmost bit). The input/output is given from the highest bit to the lowest bit.

Here is an example:

Binary String	$\tt{011}$
Bit $2$	$\tt{0}$
Bit $1$	$\tt{1}$
Bit $0$	$\tt{1}$

Problem Background

Unconsciously, it was already 7 PM—just one hour left until the lottery sales closed for the day.

Suddenly, the C-team coach mysteriously invited Sleeping Dolphin to buy a certain lottery ticket, claiming he had insider information. He admitted that he had made his fortune and became the C-team coach through lottery winnings.

"So this is why the C-team is in such a mess!" Sleeping Dolphin suppressed his anger and accompanied the C-team coach to buy the lottery.

Problem Description

The C-team coach told Sleeping Dolphin that a certain lottery uses the mt1.9937 algorithm for drawing numbers. The random number generation strategy of this algorithm is as follows:

1. Read the current random seed $S$ ($S$ is an $n$-bit binary string).
2. Define a new binary string $T$, initially equal to $S$.
3. Repeat the following operation $k$ times: take the first bit of $T$ and append it to the end.
4. The binary string $R = S \text{ xor } T$ is converted to a binary number, which serves as the generated random number.

Now, Sleeping Dolphin has reconstructed the binary string $R$ from the previous lottery results and asks you to further reconstruct the random seed $S$.

Input Format

The first line contains two positive integers $n, k\ (1 \le n \le 10^6, 1 \le k \le 10^9)$.

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

Output Format

Output a binary string $S$ of length $n$.

The data guarantees a solution, but there may be multiple answers. Output any valid one.

Samples

4 3
1100

1000

6 9
100100

100000

8 8
00000000

10000000

Sample 1 Explanation

According to the problem description, mt1.9937 generates the random number as follows:

1. Read the current random seed $S=\tt{1000}$ ($S=\tt{1000}$ is an $n=4$-bit binary string).
2. Define a new binary string $T$, initially equal to $S=\tt{1000}$.
3. Repeat the following operation $k=3$ times: take the first bit of $T$ and append it to the end—
   • 1st operation: $\tt{\color{red}1\color{black}000}\to\tt{\color{black}000\color{red}1}$.
   • 2nd operation: $\tt{\color{red}0\color{black}001}\to\tt{\color{black}001\color{red}0}$.
   • 3rd operation: $\tt{\color{red}0\color{black}010}\to\tt{\color{black}010\color{red}0}$.
4. The binary string $R = S \text{ xor } T$ is converted to a binary number as the generated random number:

$$\tiny\begin{aligned}\normalsize\tt{1000} \\\\\normalsize\tt{xor\hspace{1.05em}0100}\\\sout{\color{transparent}\texttt{123123123123123123}}\\\normalsize\tt{1100}\end{aligned}$$

Thus, $S=\tt{1000}$ satisfies the requirement.

In fact, there are two correct answers for this sample. The other one is $S=\tt{0111}$.

Official Solution

link