5. Порядок жизни
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует известная математическая игра «Жизнь», правила которой очень просты. Дано клетчатое поле, в котором $$$n$$$ строк по $$$m$$$ столбцов в каждой. Каждая клетка может иметь одно из двух состояний: она или жива, или мертва. У клетки может быть максимум 8 соседей (если клетка не находится на краях поля). Клетки постоянно конкурируют за существование, и на каждом шаге игры происходят следующие изменения:

  1. Живая клетка, имеющая двух или трёх живых соседей, остаётся живой. Иначе она погибает от перенаселения или одиночества.
  2. Мёртвая клетка, имеющая трёх живых соседей, оживает.

Игра заканчивается, когда поле перестаёт меняться. Это состояние назовём стабилизацией.

Известно, что на симуляторе игры в «Жизнь» была запущена некоторая первоначальная конфигурация, которая стабилизировалась после некоторого числа шагов. Симулятор зафиксировал положение клеток в $$$k$$$ позициях игры, однако оказался сломан и выдал их в перемешанном порядке.

Вам необходимо определить, в каком порядке в ходе игры появлялись данные конфигурации поля. Гарантируется, что искомая перестановка единственна. Гарантируется, что игра завершится не более чем за 2000 ходов, начав своё существование со стартового положения искомой перестановки.

Входные данные

Первая строка содержит одно натуральное число $$$k$$$ ($$$1 \leq k \leq 100$$$) — количество зафиксированных конфигураций поля.

Вторая строка содержит одно натуральное число $$$n$$$ — количество строк поля.

Третья строка содержит одно натуральное число $$$m$$$  — количество столбцов. Гарантируется, что $$$1 \leq n \cdot m \leq 5000$$$.

Далее идут $$$k$$$ описаний зафиксированных конфигураций поля. Каждая конфигурация описывается $$$n$$$ строками по $$$m$$$ чисел в каждой, разделённых пробелом. Если клетка жива, то она кодируется цифрой $$$1$$$, иначе — цифрой $$$0$$$.

Выходные данные

Необходимо вывести перестановку натуральных чисел от $$$1$$$ до $$$k$$$ — в каком порядке появлялись данные конфигурации во время игры.

Система оценки

Каждый тест оценивается независимо. Тесты разбиты на группы, соответствующие следующим подзадачам:

ПодзадачаДополнительные условияБаллы
$$$1$$$$$$k=2$$$, в одной из конфигураций все клетки мёртвы5
$$$2$$$$$$k \leq 10; n, m \leq 20$$$35
$$$3$$$-60
Примеры
Входные данные
3
3
3
1 0 0
0 1 0
1 0 0
0 0 0
1 1 0
0 0 0
0 0 0
0 0 0
0 0 0
Выходные данные
1 2 3
Входные данные
2
2
3
1 0 0
1 1 0
1 0 1
1 1 0
Выходные данные
2 1