P12925 [POI 2022/2023 R2] 病毒 / Wirus

翻译来自于 [LibreOJ](https://loj.ac/p/5020)。

**题目译自 [XXX Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi30-2/dashboard/) [Wirus](https://szkopul.edu.pl/problemset/problem/c9kbLOJVLHiQDcmiNo8Pa4w6/statement/)** 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$ 天后病毒的基因型，格式与输入相同。

**样例 1 解释** 病毒基因型每日变化如下： $$ 01010 \to 10101 \to 01011 \to 10111 \to 01111 $$ **附加样例** 1. $n=10, d=30$，初始基因型 $1010000101$，答案为 $0110110110$。 2. $n=100, d=2000000$，初始基因型 $000\ldots000$，答案为 $000\ldots000$。 3. $n=700, d=10^{15}$，初始基因型 $111\ldots111$。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $d \leq 100$ | $7$ | | $2$ | $d \leq 2000000$ | $12$ | | $3$ | $n \leq 100$ | $65$ | | $4$ | 无附加限制 | $16$ |