负责人

• 035966_L3

注意

本题需要文件读写（lottery.in / lottery.out）。

本题中 01 串的下标从 $\bm{0}$ 开始计数，并且在输入 / 输出时从高位到低位给出。

以下是一个例子：

01 串	$\tt{011}$
第 $2$ 位	$\tt{0}$
第 $1$ 位	$\tt{1}$
第 $0$ 位	$\tt{1}$

题目背景

不知不觉中，时间已经来到了晚上 $7$ 点——再有 $1$ 个小时，今天的彩票就要停售了。

突然，C 队主帅神秘地邀请 Sleeping Dolphin 去买某种彩票，并说他有内部消息——据他自己坦白，他当年就是靠彩票发家并当上 C 队主帅的。

「C 队如此狼狈的原因原来是这样啊！」Sleeping Dolphin 极力掩盖住自己的愤怒，陪 C 队主帅去买彩票了。

题目描述

C 队主帅告诉 Sleeping Dolphin，某种彩票使用 mt1.9937 作为摇奖算法。这个算法的随机数生成策略如下：

1. 读取当前的随机数种子 $S$（$S$ 是一个 $n$ 位 01 串）。
2. 定义一个新的 01 串 $T$，其初值为 $S$。
3. 重复执行以下操作 $k$ 次：取出 $T$ 的第一位，然后放到末尾。
4. 将 01 串 $R=S \text{ xor } T$ 所对应的二进制数作为本次生成的随机数。

现在，Sleeping Dolphin 利用上一期开奖结果复原出了 01 串 $R$，并要求你进一步复原出随机数种子 $S$。

输入格式

第一行两个正整数 $n,k$。

第二行一个长度为 $n$ 的 01 串 $R$。

输出格式

一行一个长度为 $n$ 的 01 串 $S$。

数据保证有解，但答案可能有多个，输出一个即可。

样例

4 3
1100

1000

6 9
100100

100000

8 8
00000000

10000000

样例 1 解释

根据题目描述，mt1.9937 将会按如下步骤生成随机数：

1. 读取当前的随机数种子 $S=\tt{1000}$（$S=\tt{1000}$ 是一个 $n=4$ 位 01 串）。
2. 定义一个新的 01 串 $T$，其初值为 $S=\tt{1000}$。
3. 重复执行以下操作 $k=3$ 次：取出 $T$ 的第一位，然后放到末尾——
   • 第 $1$ 次：$\tt{\color{red}1\color{black}000}\to\tt{\color{black}000\color{red}1}$。
   • 第 $2$ 次：$\tt{\color{red}0\color{black}001}\to\tt{\color{black}001\color{red}0}$。
   • 第 $3$ 次：$\tt{\color{red}0\color{black}010}\to\tt{\color{black}010\color{red}0}$。
4. 将 01 串 $R=S \text{ xor } T$ 所对应的二进制数作为本次生成的随机数：

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

因此 $S=\tt{1000}$ 满足题意。

实际上，该样例有两个正确答案，另一个是 $S=\tt{0111}$。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le k \le 10^9$。

官方题解

link