问题描述

太郎君来到一个广场上寻找宝藏。

这个广场上，在水平方向上有 $n$ 条线，在垂直方向上有 $m$ 条线，且这些线都是等间距的。相邻线之间的距离为 $1$。
第 $i$ 条水平线从上往下数第 $i$ 条；第 $j$ 条垂直线从左往右数第 $j$ 条。这两条线的交点位置用 $(i, j)$ 表示，这个位置埋藏了 $k$ 种宝藏中的一种。

由于太郎君拥有最先进的设备，所以他知道每个位置埋藏的宝藏类型。
于是，太郎君想要查询广场上不同矩形区域的宝藏情况，即某个区域内有哪些类型的宝藏最多。

然而，次郎君经常恶作剧，交换相邻的宝藏位置。
这里所谓的相邻宝藏指的是，两个宝藏的位置之间的距离正好为 $1$。

请代替困扰于次郎君的太郎君，对给定的每个区域，找出区域内包含的最多宝藏类型及其数量。

输入

输入以以下格式给出。

$n$ $m$ $k$ $a_{1,1}$ $a_{1,2}$ $...$ $a_{1,m}$ $...$ $a_{n,1}$ $a_{n,2}$ $...$ $a_{n,m}$ $q$ $t_1$ $x_{11}$ $y_{11}$ $x_{21}$ $y_{21}$ $...$ $t_q$ $x_{1q}$ $y_{1q}$ $x_{2q}$ $y_{2q}$

• 第 $1$ 行包含 $3$ 个整数 $n$ ($1 \\leq n \\leq 500$)、$m$ ($1 \\leq m \\leq 500$) 和 $k$ ($1 \\leq k \\leq 100$)，分别表示广场上水平线的数量、垂直线的数量和埋藏的宝藏类型数量。
• 接下来的 $n$ 行，每行包含 $m$ 个整数，表示广场上各位置埋藏的宝藏类型。
• $a_{i,j}$ ($1 \\leq a_{i,j} \\leq k$) 表示广场上位置 $(i, j)$ 埋藏的宝藏类型。
• 第 $n + 2$ 行包含一个整数 $q$ ($1 \\leq q \\leq 100{,}000$)，表示查询的数量。
• 接下来的 $q$ 行，每行包含一个查询的信息。
• $t_i$ ($1 \\leq t_i \\leq 2$) 表示第 $i$ 个查询的类型。
• 当 $t_i = 1$ 时，表示第 $i$ 个查询为次郎君交换宝藏的操作，表示位置 $(x_{1i}, y_{1i})$ 和位置 $(x_{2i}, y_{2i})$ 的宝藏被交换。
• 当 $t_i = 1$ 时，保证位置 $(x_{1i}, y_{1i})$ 和位置 $(x_{2i}, y_{2i})$ 是相邻的。
• 当 $t_i = 2$ 时，表示第 $i$ 个查询为查询当前宝藏情况的操作，表示以位置 $(x_{1i}, y_{1i})$ 和 $(x_{2i}, y_{2i})$ 为对角线顶点的矩形区域内的宝藏情况。
• 当 $t_i = 2$ 时，保证 $x_{1i} \\leq x_{2i}$ 且 $y_{1i} \\leq y_{2i}$。
• 对于每个查询，保证 $1 \\leq x_{1i}, x_{2i} \\leq n$ 且 $1 \\leq y_{1i}, y_{2i} \\leq m$。

输出

对于每个类型为 $2$ 的查询，输出一行，表示该查询所代表的矩形区域内包含的最多宝藏类型及其数量。

如果有多个最多宝藏类型，则输出其中宝藏类型编号最大的。

末尾输出一个换行符，不要输出多余的字符和空行。

输入示例1

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

输出示例1

2 3
1 3
3 2

输入示例2

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

输出示例2

1 1
2 2