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

Условие

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

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

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

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

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

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

Ограничения

1 ⩽ N,M ⩽ 100

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

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

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

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

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