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