Контекст задачи
Знаменитый математик Джон Х. Конвей (1937–2020) скончался во время пандемии COVID-19. Его научные интересы охватывали комбинаторные игры, теорию групп и многие другие области; он внес значительный вклад в классификацию конечных групп, теорию клеточных автоматов и комбинаторные игры. Он также занимался популяризацией математики и разработал «Игру в жизнь» (Conway's Game of Life), ставшую всемирно известной.
Сегодня давайте вспомним одно из его самых известных изобретений.
Правила «Игры в жизнь» следующие:
- Существует квадратная сетка, в каждой ячейке которой находится клетка. Клетка может быть в одном из двух состояний: мертвая или живая. Состояние каждой клетки в следующий момент времени однозначно определяется её текущим состоянием и состояниями 8 соседних клеток.
- Если текущая клетка жива и у неё меньше 2 живых соседей, она умирает.
- Если текущая клетка жива и у неё 2 или 3 живых соседа, она остается в том же состоянии.
- Если текущая клетка жива и у неё более 3 живых соседей, она умирает.
- Если текущая клетка мертва и у неё ровно 3 живых соседа, она становится живой, в противном случае остается мертвой.
Условие задачи
Из-за ограничений памяти компьютера мы не можем моделировать «Игру в жизнь» на бесконечной сетке, поэтому мы рассматриваем только сетку $4\times 4$, считая, что за пределами сетки клетки не могут быть живыми.
Вам предстоит обработать $Q$ запросов. В каждом запросе дается состояние каждой ячейки сетки $4\times 4$. Требуется определить состояние каждой ячейки сетки через $T$ моментов времени.
Входные данные
Данные поступают из стандартного ввода.
В первой строке вводится целое положительное число $Q$, количество запросов.
Далее следуют $5Q$ строк, по 5 строк на каждый запрос.
Первые 4 строки каждого запроса содержат строку из 4 символов 01, описывающую состояние клеток сетки, где 0 означает мертвую клетку, а 1 — живую. Следующая строка содержит целое положительное число $T$, количество прошедших моментов времени.
Выходные данные
Результат выводится в стандартный вывод.
Выведите $4Q$ строк, по 4 строки на каждый запрос.
Ответ на каждый запрос представляет собой 4 строки, каждая из которых содержит строку из 4 символов 01, описывающую состояние клеток сетки, где 0 означает мертвую клетку, а 1 — живую.
Примеры
Пример 1
1 0000 1100 0110 0000 3
Выходные данные 1
0100 1010 1010 0100
Примечание 1
Через один момент времени состояние сетки становится:
0000 1110 1110 0000
Еще через один момент времени состояние сетки становится:
0100 1010 1010 0100
Затем следующее состояние будет таким же, как текущее, то есть в последующие моменты времени состояние будет оставаться неизменным. Таким образом, через 3 момента времени состояние будет именно таким.
Пример 2
См. файлы ex_2.in и ex_2.ans в директории загрузки.
Подзадачи
Для 100% данных гарантируется $Q \le 10^{4}, T \le 10^{9}$.
| Тест | $Q$ | $T$ |
|---|---|---|
| 1, 2, 3, 4 | $= 10^{2}$ | $\le 10^{2}$ |
| 5, 6, 7 | $= 10^{3}$ | $\le 10^{3}$ |
| 8, 9 | $= 10$ | $\le 10^{9}$ |
| 10 | $= 10^{4}$ | $\le 10^{9}$ |