You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

提示

样例解释 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 位整数。