William 非常喜欢名为“生命游戏”的元胞自动机,因此他决定制作自己的版本。为了简单起见,William 决定在包含 $$$n$$$ 个单元的数组上定义他的元胞自动机,每个单元要么是活的,要么是死的。
威廉元胞自动机中数组的演化按以下方式迭代发生:
- 如果该元素已死亡,并且在数组的当前状态下恰好有 $$$1$$$ 存活邻居,则在下一次迭代时它将变为活动状态。对于索引 $$$i$$$ 处的元素,邻居将是索引为 $$$i - 1$$$ 和 $$$i + 1$$$ 的元素。如果该索引处没有元素,则将其视为死邻居。
- 威廉是一个仁慈的人,所以所有活着的元素都活着。
检查注释部分以获取演变的示例。
给定了所有元素的一些初始状态,您需要帮助 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$$$ 进化迭代后数组的状态。
示例
输入 #1
4 11 3 01000000001 10 2 0110100101 5 2 10101 3 100 000
输出 #1
11111001111 1110111101 10101 000
注意
第一个测试用例的迭代演化序列
- 01000000001 — 初始状态
- 11100000011 — 进化的第一次迭代
- 11110000111 — 进化的第二次迭代
- 11111001111 — 进化的第三次迭代
第二个测试用例的迭代演化序列
- 0110100101 — 初始状态
- 1110111101 — 进化的第一次迭代
- 1110111101 — 进化的第二次迭代