Василию очень нравится клеточный автомат «Game of life», поэтому он решил попробовать придумать что-то подобное. Для простоты, Василий решил определить свой клеточный автомат на массиве из \(n\) ячеек, каждый элемент которого может быть в живом или неживом состоянии.
Эволюция массива в клеточном автомате Василия происходит итеративно следующим образом:
- Если у неживого элемента есть ровно \(1\) живой сосед в текущем состоянии массива, то на следующей итерации он станет живым. Соседями для элемента на позиции \(i\) являются элементы на позициях \(i - 1\) и \(i + 1\), если соседа на такой позиции не существует, то считается, что он мертв.
- Василий — гуманист, поэтому все живые элементы в его автомате остаются живыми.
Смотрите секцию примечание для примеров эволюции.
Вам дано некоторое начальное состояние всех элементов, и вам нужно помочь Василию определить, каким будет состояние массива через \(m\) итераций эволюции.
Выходные данные
Для каждого набора входных данных выведите строку из \(n\) символов «0» и «1» — состояние массива через \(m\) итераций эволюции.
Примечание
Последовательность итераций эволюции для первого набора данных:
- 01000000001 — начальное состояние
- 11100000011 — первая итерация эволюции
- 11110000111 — вторая итерация эволюции
- 11111001111 — третья итерация эволюции
Последовательность итераций эволюции для второго набора данных:
- 0110100101 — начальное состояние
- 1110111101 — первая итерация эволюции
- 1110111101 — вторая итерация эволюции
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 -1 152 426 1 3.627689584601 3.577721408504 2.198599748243
0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 -1 141 217 -1 1.714712084927 4.034616670416 5.587944088527
3 0 1 0 17 6 11 2 11 16 10 3 0 1 0 0
17 19:00 333 444 7 3.242665536417 3.714271486813 2.242156197892
2 4 1 0 7 12 4 8 11 -1 -1 -1 -1 -1 -1 0
|
DRAW
HOME
AWAY
|