Василию очень нравится клеточный автомат «Game of life», поэтому он решил попробовать придумать что-то подобное. Для простоты, Василий решил определить свой клеточный автомат на массиве из $$$n$$$ ячеек, каждый элемент которого может быть в живом или неживом состоянии.
Эволюция массива в клеточном автомате Василия происходит итеративно следующим образом:
- Если у неживого элемента есть ровно $$$1$$$ живой сосед в текущем состоянии массива, то на следующей итерации он станет живым. Соседями для элемента на позиции $$$i$$$ являются элементы на позициях $$$i - 1$$$ и $$$i + 1$$$, если соседа на такой позиции не существует, то считается, что он мертв.
- Василий — гуманист, поэтому все живые элементы в его автомате остаются живыми.
Смотрите секцию примечание для примеров эволюции.
Вам дано некоторое начальное состояние всех элементов, и вам нужно помочь Василию определить, каким будет состояние массива через $$$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$$$ итераций эволюции.
4 11 3 01000000001 10 2 0110100101 5 2 10101 3 100 000
11111001111 1110111101 10101 000
Последовательность итераций эволюции для первого набора данных:
- 01000000001 — начальное состояние
- 11100000011 — первая итерация эволюции
- 11110000111 — вторая итерация эволюции
- 11111001111 — третья итерация эволюции
Последовательность итераций эволюции для второго набора данных:
- 0110100101 — начальное состояние
- 1110111101 — первая итерация эволюции
- 1110111101 — вторая итерация эволюции
