开始: 2024-04-14 14:30:00

20240414

结束: 2024-04-14 17:30:00
当前: 2025-0606-0707 23:46:18  类型:单人排位赛 状态:已经结束 
P5 : A-山峰  
描述

nm 列的土地,第 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_1y_1 列的土地与 x_2y_2 列的土地发生了地理变迁。
对于 100\% 的数据, 1 \le n,m \le 500, 0 \le T \le 10^4, 1 \le a_{i,j} \le 10^4, 1\le x_1,x_2\le n, 1\le y_1,y_2\le m

输出

输出的第一行为一个整数,代表地理变迁后山峰的数量 k。 
接下来 k 行,每行两个整数 x,y,代表一座山峰在第 x 行第 y 列。 
如果有多座山峰,输出时按行号从小到大输出,行号相同时按列号从小到大输出。

样例

输入

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

输出

2
1 3
2 2

输入

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

输出

2
1 3
2 2