题目描述

某 E 刚结束军训，军训教官将所有同学排成了 $n$ 行 $m$ 列。

教官组织同学们进行分列式练习，同学们将按行为单位进行练习。第 $i$ 行第 $j$ 名同学摆臂的高度为 $a_{i,j}$，踢腿的高度为 $b_{i,j}$。

教官认为，每一行同学的不整齐度为摆臂高度方差与踢腿高度方差之和。形式化的，第 $i$ 行同学的不整齐度为

$$\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} $$

其中，$\sum\limits_{j=1}^m{a_{i,j}}$ 代表 $a_{i,1}+a_{i,2}+a_{i,3}+\cdots+a_{i,m}$。

教官希望对若干行进行位置上的对调，使得最终排出的方阵中，从第 $1$ 行至第 $n$ 行不整齐度依次递增。若有两行不整齐度相同，可以任意安排其顺序。

请你编写程序，给出一种交换方案。请注意，每一步交换是即刻完成的。

例如，给出如下的交换方案：

第一步，交换第 $1$ 行和第 $2$ 行；第二步，交换第 $2$ 行和第 $3$ 行。

初始：

当前行数	初始行号
$1$
$2$
$3$

第一步完成后：

当前行数	初始行号
$1$	$2$
$2$	$1$
$3$

第二步完成后：

当前行数	初始行号
$1$	$2$
$2$	$3$
$3$	$1$

提示：例如，将第 $1$ 行与第 $3$ 行交换后，原第 $1$ 行将被叫做第 $3$ 行，而不是仍被叫做第 $1$ 行。

具体解释可参照样例 #2 解释。

输入格式

输入共 $2n+1$ 行。

输入的第一行为两个整数 $m,n$，分别代表列数和行数。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个代表 $a_{i,j}$。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个代表 $b_{i,j}$。

输出格式

输出若干行。

输出的第一行为一个整数 $K$，代表你交换方案中交换的次数。

接下来 $K$ 行，每行输出两个整数 $x,y$，代表将第 $x$ 行与第 $y$ 行的同学进行交换。

注意：$K$ 应当不超过 $n^2$。

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

3
1 2
1 3
2 3

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

3
1 2
2 3
1 2

提示

样例 #2 解释

仅考虑摆臂高度，在前两次交换后，阵列变成如下的样子：

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

此时，原第 $3$ 行现被叫做第 $2$ 行，原第 $2$ 行现被叫做第 $1$ 行。如果我们想要将它们交换，应该输出 1 2 而不是 2 3。

数据规模与约定

对于 $30\%$ 的数据，所有 $a_{i,j}$ 均相同，$b_{i,j}$ 均相同。

对于另外 $20\%$ 的数据，满足 $n\le 100,m\le 100$。

对于 $100\%$ 的数据，$1 \le n,m \le 1000, 1 \le a_{i,j},b_{i,j} \le 100$。

Special Judge

本题答案不唯一，将有 Special Judge 对你的答案进行检查，所有合法答案均可以得分。

Problem Assigned by 览遍千秋 | 七海