5. Order of Life
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a well-known mathematical game called "Life," the rules of which are very simple. Given a grid with $$$n$$$ rows and $$$m$$$ columns. Each cell can have one of two states: it is either alive or dead. A cell can have a maximum of 8 neighbors (if it is not located on the edges of the grid). Cells constantly compete for existence, and at each step of the game, the following changes occur:

  1. A living cell with two or three living neighbors remains alive. Otherwise, it dies from overpopulation or loneliness.
  2. A dead cell with three living neighbors comes to life.

The game ends when the grid stops changing. We will call this state stabilization.

It is known that a certain initial configuration was launched on the "Life" game simulator, which stabilized after a certain number of steps. The simulator recorded the positions of the cells in $$$k$$$ game states, but it broke and output them in a mixed order.

You need to determine the order in which these configurations of the grid appeared during the game. It is guaranteed that the sought permutation is unique. It is also guaranteed that the game will finish in no more than 2000 moves, starting from the initial position of the sought permutation.

Input

The first line contains a single natural number $$$k$$$ ($$$1 \leq k \leq 100$$$) — the number of recorded configurations of the grid.

The second line contains a single natural number $$$n$$$ — the number of rows in the grid.

The third line contains a single natural number $$$m$$$ — the number of columns. It is guaranteed that $$$1 \leq n \cdot m \leq 5000$$$.

Next, there are $$$k$$$ descriptions of the recorded configurations of the grid. Each configuration is described by $$$n$$$ lines with $$$m$$$ numbers in each, separated by spaces. If a cell is alive, it is encoded by the digit $$$1$$$, otherwise — by the digit $$$0$$$.

Output

You need to output a permutation of natural numbers from $$$1$$$ to $$$k$$$ — in what order the given configurations appeared during the game.

Scoring

Each test is evaluated independently. The tests are divided into groups corresponding to the following subtasks:

SubtaskAdditional ConditionsPoints
$$$1$$$$$$k=2$$$, in one of the configurations all cells are dead5
$$$2$$$$$$k \leq 10; n, m \leq 20$$$35
$$$3$$$-60
Examples
Input
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
Output
1 2 3
Input
2
2
3
1 0 0
1 1 0
1 0 1
1 1 0
Output
2 1