#2228. 赛码集训营之积分大师

赛码集训营之积分大师

题目背景

在赛码集训营的每一天,选手们都可以获得一定量的保底积分,当然也通过回答问题,在比赛中取得好成绩等方式获取额外积分。

题目描述

赛码集训营已经接近尾声了,集训营的金牌选手正在运动场做操,选手们站成一个nnmm 列的队伍,第 ii 行第 jj 列的选手积分为 ai,ja_{i,j}。行号和列号均从 11 开始编号。

在集合的过程中,同学们的位置会发生一些变化,一共发生了 TT 次改变。每次改变位置,那么选手所对应的积分也会随之改变。

如果有一个同学的积分,比前后左右直接相邻的同学积分都高,我们称其为一个Luck star。

赛码想要知道,在所有位置变化完成后,一共有多少选手是Luck star,他们的坐标分别为多少。

例如:n=m=3n=m=3,积分如下所示

1  2  31  4  21  1  21 \ \ 2 \ \ 3 \\ 1 \ \ 4 \ \ 2\\ 1 \ \ 1 \ \ 2

其中,(1,3),(2,2)(1,3),(2,2) 是Luck star。

输入格式

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

接下来 nn 行,每行 mm 个整数,第 ii 行第 jj 个整数代表 ai,ja_{i,j}

接下来一行一个整数 TT

接下来 TT 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,代表 x1x_1y1y_1 列的选手与 x2x_2y2y_2 列的选手发生了位置交换。

输出格式

输出的第一行为一个整数,代表位置交换后Luck star的数量 kk

接下来 kk 行,每行两个整数 x,yx,y,代表一个Luck star在第 xx 行第 yy 列。

按照从上到下,自左向右的顺序输出Luck star的坐标。

样例 #1

样例输入 #1

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

样例输出 #1

2
1 3 
2 2

样例 #2

样例输入 #2

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

样例输出 #2

2
1 3
2 2

提示

对于 20%20\% 的数据,n=1n=1; 对于另外 20%20\% 的数据,m=1m=1; 对于另外 20%20\% 的数据,n=mn=m; 对于另外 20%20\% 的数据,T=0T=0; 对于 100%100\% 的数据, $1 \le n,m \le 1000, 0 \le T \le 10^5, 1 \le a_{i,j} \le 10^6, 1\le x_1,x_2\le n, 1\le y_1,y_2\le m$。