[CCC2016] 生命中的圆

题目描述

**译自 [CCC2016](https://cemc.math.uwaterloo.ca/contests/computing/2016/index.html) Senior T5「[Circle of Life](https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf)」** > 也许你听说过康威生命游戏(Conway's Game of Life)。康威生命游戏适用于方格组成的矩阵。但它可以产生十分复杂的结构。在这道题目中,我们将使用简化版的生命游戏来虐你。 这个游戏是 0 人游戏,换句话说,只要给定初始条件,这个游戏就能自己进行下去。 将一个圆环分为 $N$ 段,将这 $N$ 段顺时针依次编为 $1,\dots,N$ 号。每一段要么是活的(以 `1` 表示),要么是死的(以 `0` 表示)。 游戏会进行 $T$ 轮「变化」。如果一个方格**恰好**有一个相邻的方格在这次变化中存活,那么该方格会在下次变化中存活。否则,该方格会死亡。 给定圆环的初始状态,求经过 $T$ 次变化之后的状态。

输入输出格式

输入格式


第一行,两个整数 $N$ 和 $T(3 \le N \le 100\ 000;1 \le T \le 10^{15})$。 第二行,一个长度为 $N$ 的字符串,表示 $N$ 个方格的初始状态。保证每个字符只有 `0` 或 `1` 两种可能。第 $i$ 位表示编号为 $i$ 的方格的初始状态。

输出格式


输出一个长度为 $N$ 的字符串,表示最终的状态。格式同输入。

输入输出样例

输入样例 #1

7 1
0000001

输出样例 #1

1000010

输入样例 #2

5 3
01011

输出样例 #2

10100

说明

#### 样例解释 1 方格 $1$ 和 $N - 1$ 和 $N$ 相邻,因此在一次变化后仍存活。 #### 样例解释 2 一次变化后,状态为 ` 00011`。 两次变化后,状态为 ` 10111`。 对于 $\frac{1}{15}$ 的数据,$N \le 15,T \le 15$。 对于另外的 $\frac{6}{15}$ 的数据,$N \le 15$。 对于另外的 $\frac{4}{15}$ 的数据,$N \le 4000,T \le 10\ 000\ 000$。 注意对于所有的数据,你需要使用 64 位整数。