В некоторых клетках квадрата \( N\ х\ N\) живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через \(T\) секунд.
Входные данные: В первой строке вводятся два натуральных числа –
\( N\) (
\(1 \leq N \leq 10\)) и
\(T\) (
\(1 \leq T \leq 100\)). Далее записано
\( N\) строчек по
\( N\) чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.
Выходные данные: Требуется вывести
\( N\) строк по
\( N\) чисел – описание конфигурации через T секунд (в том же формате, как и во входных данных).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 1
1 0 1
1 0 1
1 0 1 |
0 0 0
1 0 1
0 0 0 |
| 2 |
2 2
1 1
1 1 |
1 1
1 1 |
| 3 |
5 10
1 0 1 1 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 1 0 |
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 |