题目描述

There are $M$ balls of each color $1, 2, \ldots, N$, and $N$ students are sitting in a circle playing with these balls. The students are numbered from $1$ to $N$ in the order in which they are seated.

Initially, each student has exactly $M$ balls. Specifically, the color of the $j$-th ball that $i$-th student has is color $a_{i,j}$. They will perform the following operation to achieve a state where each student holds balls of only one color:

Operation: Each of the $N$ students simultaneously passes one ball they currently possess to their neighbor (the $i$-th student passes a ball to the $(i + 1)$-th student, and the $N$-th student passes a ball to the $1$st student, as the $(N + 1)$-th student is considered to be the $1$st student).

Your task is to determine whether, by repeating this operation at most $NM$ times, it is possible to achieve the goal. If possible, output a sequence of operations.

输入格式

The input consists of a single test case of the following format.

$$\begin{aligned} & N \ M \\ & a_{1,1} \ a_{1,2} \ \ldots \ a_{1,M} \\ & a_{2,1} \ a_{2,2} \ \ldots \ a_{2,M} \\ & \vdots \\ & a_{N,1} \ a_{N,2} \ \ldots \ a_{N,M} \end{aligned}$$

The first line contains two integers $N$ and $M$, where $N$ represents the number of students and $M$ represents the number of balls of each color. Both $N$ and $M$ are between $2$ and $100$ (for $N$) and $2$ and $100$ (for $M$), inclusive.

Each of the following $N$ lines consists of $M$ positive integers $a_{i,1}, a_{i,2}, \ldots, a_{i,M}$. The integer $a_{i,j}$ represents the color of the $j$-th ball that the $i$-th student initially has. It is guaranteed that $1 \leq a_{i,j} \leq N$ and that each integer $1, 2, \ldots, N$ occurs $M$ times among $a_{i,j} \ (1 \leq i \leq N, 1 \leq j \leq M)$.

It is also guaranteed that the initial state does not satisfy the goal condition.

输出格式

Print $-1$ if it is impossible to achieve the goal state by at most $NM$ operations.

Otherwise, print $K$ — the number of operations. In the following $K$ lines, print $N$ integers $c_{i,1}, c_{i,2}, \ldots, c_{i,N}$. Here, $c_{i,j}$ represents the color of the ball passed from the $j$-th student to the $(j+1)$-th student at the $i$-th operation.

2 4
1 2 1 2
2 1 2 1

2
1 2
1 2

3 3
1 2 3
2 3 1
3 1 2

3
2 3 1
3 1 2
2 3 1