题目描述

探索者号将一片星域划分为 $n$ 行 $m$ 列的观测网格，第 $i$ 行第 $j$ 列的初始能量为 $a_{i,j}$。行号和列号均从 $1$ 开始编号。

在漫长的观测中，一共发生了 $T$ 次能量潮汐。每次能量潮汐，两个网格单元的能量会发生交换。

如果一个网格单元的能量，严格大于其上下左右直接相邻网格单元的能量，则称其为一个“信标点”。

探索者号想要知道，在所有能量潮汐完成后，星域中一共有多少个信标点，它们的坐标分别是什么。

例如：$n=m=3$，能量分布如下：

$$1 \ \ 2 \ \ 3 \\ 1 \ \ 4 \ \ 2 \\ 1 \ \ 1 \ \ 2$$

其中，$(1,3),(2,2)$ 是信标点。

输入格式

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

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

接下来一行一个整数 $T$。

接下来 $T$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，代表第 $x_1$ 行第 $y_1$ 列的网格单元与第 $x_2$ 行第 $y_2$ 列的网格单元发生了能量交换。

输出格式

输出的第一行为一个整数，代表能量交换后信标点的数量 $k$。

接下来 $k$ 行，每行两个整数 $x,y$，代表一个信标点在第 $x$ 行第 $y$ 列。

你可以以任意顺序输出信标点的坐标。

输入输出样例

3 3
1 5 1
2 3 2
4 1 1
0

2
1 2
3 1

3 3
4 1 1
1 5 2
1 3 2
1
1 1 3 1

2
2 2
3 1

说明/提示

对于 $20\%$ 的数据，$n=1$；
对于另外 $20\%$ 的数据，$m=1$；
对于另外 $20\%$ 的数据，$n=m$；
对于另外 $20\%$ 的数据，$T=0$；
对于 $100\%$ 的数据：

$$1 \le n,m \le 1000,\quad 0 \le T \le 10^5,\quad 1 \le a_{i,j} \le 10^6,\quad 1\le x_1,x_2\le n,\quad 1\le y_1,y_2\le m$$