C. Conveyors
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a container represented as an $$$N \times M$$$ grid. Each cell in the grid contains a type of cargo, where the cargo in row $$$i$$$ and column $$$j$$$ is denoted by $$$a_{i, j}$$$. Rows are numbered from top to bottom $$$1, 2, \ldots, N$$$; columns from left to right $$$1, 2, \ldots, M$$$. Each row is equipped with a conveyor belt. When you activate the conveyor belt in row $$$i$$$, all the cargo in that row shifts one cell to the right, with the rightmost cargo wrapping around to the leftmost cell. For example, if the row initially contains $$$[1, 2, 3, 4]$$$, after one shift it becomes $$$[4, 1, 2, 3]$$$.

In addition, there is an empty cell located above the first cell of the first column (i.e., just above $$$a_{1, 1}$$$). You can move this empty cell by swapping it with the cargo directly above or below it, as long as such a cell exists. Specifically:

  • If there is a cell below the empty cell, you may swap the empty cell with the cargo below it.
  • If there is a cell above the empty cell, you may swap the empty cell with the cargo above it.

Your goal is to perform a sequence of operations to arrange the container into a "sorted" state. A container is considered sorted if it satisfies both of the following conditions:

  • The empty cell is back at the topmost position of the first column.
  • The cargo in row $$$i$$$ and column $$$j$$$ is exactly $$$(i - 1) \cdot M + j$$$.

Determine whether it's possible to reach the sorted state. If it is, output a sequence of operations to achieve it. Otherwise, state that it's impossible.

Input

The first line of the input contains two integers $$$N$$$ and $$$M$$$, the number of rows and the number of columns.

Each of the next $$$N$$$ lines describes one row of the container. The $$$i$$$-th of these lines contains $$$M$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, M}$$$, the initial contents of row $$$i$$$.

  • $$$1 \leq N, M \leq 10$$$
  • $$$1 \leq a_{i, j} \leq N \cdot M$$$
  • All $$$a_{i,j}$$$ are distinct.
Output

If the goal is not achievable, output a single line containing $$$-1$$$.

Otherwise, on the first line outputs an integer $$$K$$$, the number of operations you need to perform.

On the second line outputs $$$K$$$ integers $$$b_1, b_2, \ldots, b_K$$$, where the $$$i$$$-th integer denotes the $$$i$$$-th operation:

  • If $$$b_i = -2$$$, swap the empty cell with the one below it.
  • If $$$b_i = -1$$$, swap the empty cell with the one above it.
  • If $$$1 \leq b_i \leq N$$$, activate the conveyor in row $$$b_i$$$.

Your answer will be considered correct if:

  • $$$0 \leq K \leq 5 \cdot 10^5$$$
  • $$$\forall 1 \leq i \leq K, b_i = -1 \lor b_i = -2 \lor 1 \leq b_i \leq N$$$
  • After performing all the operations, the container is sorted.

Note that you do not have to minimize the number of operations.

Examples
Input
2 2
1 3
4 2
Output
6
-2 1 -2 2 -1 -1
Input
2 3
1 2 3
4 5 6
Output
5
1 1 1 -2 -1
Input
2 3
1 2 3
4 6 5
Output
-1
Input
3 3
1 2 3
9 4 6
5 7 8
Output
13
-2 1 1 -2 2 -2 3 -1 2 -1 1 -1 3
Note

Below picture shows how to perform a sequence of operations to make the first sample sorted. Here, we use $$$0$$$ to represent the empty cell.