Ponyville 正在举办一年一度的数学节！能够解决这道题的小马将被授予“超级格雷小马”的荣誉。准备好迎接挑战并尽你所能吧！

在本题中，$i$ 阶格雷码定义为 $a^{(i)}$，这是一个包含 $2^i$ 个二进制数的数组，编号从 $0$ 到 $2^i - 1$。注意，在本题中，为了使每个元素都成为严格的 $i$ 位二进制数，会补上前导零。具体规则如下：

1. 对于 $i = 1$，$a^{(1)} = [0, 1]$，$a^{(1)}[0] = 0$，$a^{(1)}[1] = 1$。
2. 对于 $i > 1$，$a^{(i)}$ 的前半部分 $(a^{(i)}[0], \dots, a^{(i)}[2^{i-1} - 1])$ 可以通过在 $a^{(i-1)}$ 中每个元素的最高位前添加一个数字 $0$ 得到。
3. 对于 $i > 1$，$a^{(i)}$ 的后半部分 $(a^{(i)}[2^{i-1}], \dots, a^{(i)}[2^i - 1])$ 可以通过在 $a^{(i-1)}$ 中每个元素的最高位前添加一个数字 $1$，然后将这些元素按逆序排列得到。

例如：

• $a^{(1)} = [0, 1]$
• $a^{(2)} = [00, 01] + \text{rev}([10, 11]) = [00, 01, 11, 10]$
• $a^{(3)} = [000, 001, 011, 010] + \text{rev}([100, 101, 111, 110]) = [000, 001, 011, 010, 110, 111, 101, 100]$

给定 $S$ 和 $k$，$S_k$ 定义为：

$$S_k = \underbrace{a^{(n)}[a^{(n)}[\dots a^{(n)}}_{k \times a^{(n)}}[S] \dots]]$$

现在给定 $S$ 和 $k$，你需要计算 $S_k$ 的精确值。在本题中，$S$ 以 $n$ 位二进制数的形式给出，可能包含前导零。

输入格式

第一行包含两个整数 $n, k$ ($1 \le n \le 3 \times 10^6, 1 \le k \le 10^9$)。 第二行包含一个长度为 $n$ 的二进制数 $S$。最高位在左侧，最低位在右侧。

输出格式

输出 $S_k$，格式为一个 $n$ 位二进制数，占一行，最高位在左侧，最低位在右侧。

样例

样例输入 1

3 5
011

样例输出 1

010

说明

$a^{(3)} = [000, 001, 011, 010, 110, 111, 101, 100]$ $S_1 = a^{(3)}[(011)_2] = a^{(3)}[3] = 010$ $S_2 = a^{(3)}[(010)_2] = a^{(3)}[2] = 011$ $S_3 = a^{(3)}[(011)_2] = a^{(3)}[3] = 010$ $S_4 = a^{(3)}[(010)_2] = a^{(3)}[2] = 011$ $S_5 = a^{(3)}[(011)_2] = a^{(3)}[3] = 010$