军训

来源：洛谷 B3675（[语言月赛202210] 军训）

题目描述

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

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

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

$$\dfrac{1}{m} \times \sum_{j=1}^{m}{\left(a_{i,j}-\dfrac{\sum_{k=1}^{m}{a_{i,k}}}{m}\right)^2} + \dfrac{1}{m} \times \sum_{j=1}^{m}{\left(b_{i,j}-\dfrac{\sum_{k=1}^{m}{b_{i,k}}}{m}\right)^2}$$

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

教官希望对若干行进行位置上的对调，使得最终排出的方阵满足：对于任意 $1 \le i < j \le n$，第 $i$ 行的不整齐度不大于第 $j$ 行的不整齐度。

请你给出一种交换方案（可以交换任意次，也可以一次都不交换），使得最终方阵满足教官的要求。

输入格式

输入共 $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$。

样例 #1

样例输入 #1

3 3
1 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

样例 #2

样例输入 #2

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

样例输出 #2

3
1 2
2 3
1 2

提示

样例 #2 解释

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

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

此时，原第 $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 对你的答案进行检查，所有合法答案均可以得分。