CF1523A.Game of Life

William really likes the cellular automaton called "Game of Life" so he decided to make his own version. For simplicity, William decided to define his cellular automaton on an array containing $n$ cells, with each cell either being alive or dead.

Evolution of the array in William's cellular automaton occurs iteratively in the following way:

• If the element is dead and it has exactly $1$ alive neighbor in the current state of the array, then on the next iteration it will become alive. For an element at index $i$ the neighbors would be elements with indices $i - 1$ and $i + 1$. If there is no element at that index, it is considered to be a dead neighbor.
• William is a humane person so all alive elements stay alive.

Check the note section for examples of the evolution.

You are given some initial state of all elements and you need to help William find the state of the array after $m$ iterations of evolution.

威廉非常喜欢名为“生命游戏”（Game of Life）的元胞自动机，因此他决定设计一个自己的版本。为简化起见，威廉将其元胞自动机定义在包含 $n$ 个单元格的一维数组上，每个单元格的状态为“存活”或“死亡”。

在威廉的元胞自动机中，数组的演化以迭代方式进行，规则如下：

• 若某单元格当前为“死亡”状态，且其在当前数组状态中恰好有 1 个存活的邻居，则在下一次迭代中它将变为“存活”状态。对于索引为 $i$ 的单元格，其邻居为索引 $i - 1$ 和 $i + 1$ 处的单元格；若该索引位置不存在单元格，则视其邻居为“死亡”。
• 威廉是一个仁慈的人，因此所有当前“存活”的单元格在下一次迭代中保持存活。

有关演化的具体示例，请参阅文末的“注释”部分。

给定初始状态下所有单元格的状态，请你帮助威廉求出经过 $m$ 次演化迭代后数组的状态。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 10^3, 1 \le m \le 10^9$), which are the total number of cells in the array and the number of iterations.

The second line of each test case contains a string of length $n$ made up of characters "0" and "1" and defines the initial state of the array. "1" means a cell is alive and "0" means it is dead.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

In each test case output a string of length $n$, made up of characters "0" and "1" — the state of the array after $m$ iterations of evolution.

在每个测试用例中，输出一个长度为 $n$ 的字符串，该字符串仅由字符 “0” 和 “1” 组成——即经过 $m$ 次演化迭代后的数组状态。

Sequence of iterations of evolution for the first test case

• 01000000001 — initial state
• 11100000011 — first iteration of evolution
• 11110000111 — second iteration of evolution
• 11111001111 — third iteration of evolution

Sequence of iterations of evolution for the second test case

• 0110100101 — initial state
• 1110111101 — first iteration of evolution
• 1110111101 — second iteration of evolution

第一个测试用例的演化迭代序列

• 01000000001 — 初始状态
• 11100000011 — 第一次演化迭代
• 11110000111 — 第二次演化迭代
• 11111001111 — 第三次演化迭代

第二个测试用例的演化迭代序列

• 0110100101 — 初始状态
• 1110111101 — 第一次演化迭代
• 1110111101 — 第二次演化迭代