CF1523A Game of Life

William 非常喜欢被称为“生命游戏”的元胞自动机，因此他决定制作自己的版本。为简化问题，William 决定将他的元胞自动机定义在一个包含 $n$ 个格子的数组上，每个格子要么存活，要么死亡。 在 William 的元胞自动机中，数组的演化按如下方式迭代进行： - 如果某个格子当前是死亡状态，并且它在当前状态下恰好有 $1$ 个存活的邻居，那么在下一次迭代时它将变为存活。对于下标为 $i$ 的格子，其邻居为下标 $i-1$ 和 $i+1$ 的格子。如果该下标不存在，则视为死亡邻居。 - William 是个仁慈的人，所以所有存活的格子都会保持存活。 具体演化过程请参见提示部分的示例。 现在给定所有格子的初始状态，请你帮助 William 求出经过 $m$ 次演化后的数组状态。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^3, 1 \le m \le 10^9$），分别表示数组中格子的总数和演化的次数。 每个测试用例的第二行包含一个长度为 $n$ 的字符串，由字符 “0” 和 “1” 组成，表示数组的初始状态。“1” 表示该格子存活，“0” 表示该格子死亡。 保证所有测试用例中 $n$ 的总和不超过 $10^4$。

对于每个测试用例，输出一行，包含一个长度为 $n$ 的字符串，由字符 “0” 和 “1” 组成，表示经过 $m$ 次演化后的数组状态。

第一个测试用例的演化过程如下： - 01000000001 — 初始状态 - 11100000011 — 第一次演化 - 11110000111 — 第二次演化 - 11111001111 — 第三次演化 第二个测试用例的演化过程如下： - 0110100101 — 初始状态 - 1110111101 — 第一次演化 - 1110111101 — 第二次演化 由 ChatGPT 4.1 翻译