题目描述

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

样例

4
11 3
01000000001
10 2
0110100101
5 2
10101
3 100
000

11111001111
1110111101
10101
000