Problem Description

A certain E has just finished military training. The drill instructor has arranged all the students into an $n$ rows by $m$ columns formation.

The instructor organizes the students to practice the march-in-review, with the students practicing by rows. The arm swing height of the $j$-th student in the $i$-th row is $a_{i,j}$, and the leg kick height is $b_{i,j}$.

The instructor believes that the untidiness of each row is the sum of the variances of the arm swing heights and the leg kick heights. Formally, the untidiness of the $i$-th row is
$$ \dfrac{1}{m} \times \sum\limits_{j=1}^{m}{\Bigg(a_{i,j}-\dfrac{\sum\limits_{k=1}^{m}{a_{i,k}}}{m}\Bigg)^2} + \dfrac{1}{m} \times \sum\limits_{j=1}^{m}{\Bigg(b_{i,j}-\dfrac{\sum\limits_{k=1}^{m}{b_{i,k}}}{m}\Bigg)^2} $$

where $\sum\limits_{j=1}^m{a_{i,j}}$ represents $a_{i,1} + a_{i,2} + a_{i,3} + \cdots + a_{i,m}$.

The instructor wants to swap the positions of several rows so that in the final formation, the untidiness from the $1$-st row to the $n$-th row increases sequentially. If two rows have the same untidiness, their order can be arbitrary.

Please write a program to provide a swapping scheme. Note that each swap is completed immediately.

For example, given the following swapping scheme:

First step, swap the $1$-st row and the $2$-nd row; second step, swap the $2$-nd row and the $3$-rd row.

Initial:

After the first step:

After the second step:

Hint: For example, after swapping the $1$-st row with the $3$-rd row, the original $1$-st row will be called the $3$-rd row, not still called the $1$-st row.

Detailed explanation can be found in Sample #2 explanation.

Input Format

The input consists of $2n+1$ lines.

The first line contains two integers $m$ and $n$, representing the number of columns and rows, respectively.

The next $n$ lines, each containing $m$ integers, represent $a_{i,j}$.

The following $n$ lines, each containing $m$ integers, represent $b_{i,j}$.

Output Format

Output several lines.

The first line contains an integer $K$, representing the number of swaps in your swapping scheme.

The next $K$ lines, each containing two integers $x$ and $y$, represent swapping the $x$-th row with the $y$-th row.

Note: $K$ should not exceed $n^2$.

Sample Input and Output

Sample Input #1

3 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output #1

3
1 2
1 3
2 3

Sample Input #2

3 3
3 6 9
2 4 6
1 2 3
1 1 1
1 1 1
1 1 1

Sample Output #2

3
1 2
2 3
1 2

Notes

Sample #2 Explanation

Considering only the arm swing heights, after the first two swaps, the formation becomes:

$\begin{matrix} 1: & 2 & 4 & 6 \\ 2: & 1 & 2 & 3 \\ 3: & 3 & 6 & 9 \end{matrix}$

At this point, the original $3$-rd row is now called the $2$-nd row, and the original $2$-nd row is now called the $1$-st row. If we want to swap them, we should output 1 2 instead of 2 3.

Data Size and Constraints

For $30\%$ of the data, all $a_{i,j}$ are the same, and all $b_{i,j}$ are the same.

For another $20\%$ of the data, $n \le 100$ and $m \le 100$.

For $100\%$ of the data, $1 \le n, m \le 1000$ and $1 \le a_{i,j}, b_{i,j} \le 100$.

Special Judge

This problem has multiple valid answers, and a Special Judge will check your answer, allowing any valid answer to score points.

Problem Assigned by 览遍千秋 | 七海

见题面 Input 部分

见题面 Output 部分