Задача 4R. Game of Life ≡

Условие

Требуется написать программу, вычисляющую следующую итерацию игры «Жизнь». Игра проходит в прямоугольной области размером N на M, состоящей из символов точка (.), обозначающий мёртвую клетку, и решётка (#), обозначающий живую. Новое состояние каждой клетки определяется состоянием её 8 соседей по следующим правилам:

• если мёртвая клетка имеет ровно три живых соседа, она становится живой;
• если живая клетка имеет меньше двух или больше трёх живых соседей, она становится мёртвой;
• иначе состояние клетки не изменяется.

При решении задачи запрещено использовать библиотеку numpy.

Формат входных данных

Входные данные содержат текущее состояние игры.

Формат выходных данных

Выходные данные должны содержать следующую итерацию игры в том же формате.

Ограничения

1 ⩽ N,M ⩽ 100

Примеры тестов

....
.##.
.##.
....

....
.##.
.##.
....

.....
..#..
..#..
..#..
.....

.....
.....
.###.
.....
.....