题目描述

也许你听说过康威生命游戏（Conway's Game of Life）。康威生命游戏适用于方格组成的矩阵，但它可以产生十分复杂的结构。在这道题目中，我们将探讨简化版的生命游戏。

将一个圆环分为 $N$ 段，将这 $N$ 段顺时针依次编为 $1,\dots,N$ 号。每一段内有一个细胞，要么是生存状态（以 $1$ 表示），要么是死亡状态（以 $0$ 表示）。我们把每个细胞两边的细胞称作它的邻居。

在时刻 $0$，给出那些活着的细胞的位置，今后任何时刻的状态，都已经被它前面的状态按照下面的游戏规则无情地规定下来了：

在每一次"变化"中，如果一个细胞恰好有一个相邻的细胞是活着的，那么该细胞在下一次变化中就会存活（变为 $1$）；

否则，该细胞在下一次变化中就会死亡（变为 $0$）。 换句话说，对一个细胞来说，若其左邻居状态 $L$ 与右邻居状态 $R$ 满足 $L \oplus R = 1$（$\oplus$ 表示异或），则它在下一代存活；否则死亡。

游戏会进行 $T$ 轮变化。给定圆环的初始状态，求经过 $T$ 次变化之后的状态。

输入格式

第一行两个正整数 $N,\ T$，之间用空格分隔。

第二行为一个长度为 $N$ 的字符串，描述 $N$ 个细胞的初始状态，每个字符保证是 $0$ 或 $1$，第 $i$ 个字符 表示细胞 $i$ 在时刻 $0$ 的状态。

输出格式

输出一行长度为 $N$ 的字符串，表示 $T$ 次变化后每个细胞的生存状态，格式与输入相同。

7 1
0 0 0 0 0 0 1

1 0 0 0 0 1 0

数据规模与约定

对于100%的数据：1 ≤ N ≤ 10000，1 ≤ T ≤ 1000