题目描述

题目译自 XXX Olimpiada Informatyczna – II etap Wirus

Bajtosia 在 Bajtocja 最先进的生物实验室工作，她的团队研究一种新型病毒。该病毒的基因型仅由两种基因组成，记为 $0$ 和 $1$，总计 $n$ 个基因，可表示为序列 $(X_1, X_2, \ldots, X_n)$，其中每个 $X_i$ 为 $0$ 或 $1$。

不幸的是，这种病毒以独特但规律的方式变异。每天，左侧第一个基因 $X_1$ 脱离，变为 $X_1 \oplus X_2$（$\oplus$ 表示异或运算），然后附着到序列右侧。因此，基因型 $(X_1, X_2, \ldots, X_n)$ 变异后为 $(X_2, X_3, \ldots, X_n, X_1 \oplus X_2)$。

Bajtosia 需要预测病毒在 $d$ 天后的基因型。你能帮助她吗？

输入格式

第一行包含两个整数 $n$, $d$ ($2 \leq n \leq 700$, $1 \leq d \leq 10^{15}$)，分别表示基因型长度和变异天数。

第二行包含一个长度为 $n$ 的字符串，由字符 $X_1, X_2, \ldots, X_n$ ($X_i \in \{0, 1\}$) 组成，第 $i$ 个字符表示第 $i$ 个基因的类型。

输出格式

输出一行，包含长度为 $n$ 的字符串，表示 $d$ 天后病毒的基因型，格式与输入相同。

样例

输入

5 4
01010

输出

01111

病毒基因型每日变化如下：

01010 → 10101 → 01011 → 10111 → 01111

附加样例

• $n=10$, $d=30$，初始基因型 1010000101，答案为 0110110110。
• $n=100$, $d=2000000$，初始基因型 000…000，答案为 000…000。
• $n=700$, $d=10^{15}$，初始基因型 111…111。

数据范围与提示