题目描述

译自 CCC2016 Senior T5. Circle of Life

也许你听说过康威生命游戏（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$ 的字符串，表示最终的状态。格式同输入。

7 1
0000001

1000010

5 3
01011

10100

数据范围与提示

对于 $\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 位整数。