Василию очень нравится клеточный автомат «Game of life», поэтому он решил попробовать придумать что-то подобное. Для простоты, Василий решил определить свой клеточный автомат на массиве из \(n\) ячеек, каждый элемент которого может быть в живом или неживом состоянии.
Эволюция массива в клеточном автомате Василия происходит итеративно следующим образом:
Смотрите секцию примечание для примеров эволюции.
Вам дано некоторое начальное состояние всех элементов, и вам нужно помочь Василию определить, каким будет состояние массива через \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач