题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 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

提示

样例 1 解释

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

附加样例

1. $n=10, d=30$，初始基因型 $1010000101$，答案为 $0110110110$。
2. $n=100, d=2000000$，初始基因型 $000\ldots000$，答案为 $000\ldots000$。
3. $n=700, d=10^{15}$，初始基因型 $111\ldots111$。

详细子任务附加限制及分值如下表所示。