Problem Description

Taro has come to a certain plaza to search for treasures.

In this plaza, there are $ n $ horizontal lines and $ m $ vertical lines drawn at equal intervals. The distance between adjacent lines is $ 1 $. The position of the point where the $ i $-th horizontal line from the top intersects the $ j $-th vertical line from the left is represented as ($i,\ j$), and there is exactly one treasure buried there, out of $ k $ types of treasures.

Taro has the latest machinery, so he knows all about where each type of treasure is buried. Therefore, Taro is trying to investigate various rectangular regions within this plaza to find out which type of treasure is most frequently buried within those regions.

However, Jiro sometimes plays a prank and swaps the positions of adjacent treasures. Here, adjacent treasures mean the treasures whose buried points are exactly $ 1 $ unit apart.

Please help Taro, who is troubled by Jiro's pranks, by finding the most frequent type of treasure in each given region at that time.

Input Format

The input is given in the following format:

$ 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} $

• The first line contains integers representing the number of horizontal lines $ n $ ($1\ \leq\ n\ \leq\ 500$), the number of vertical lines $ m $ ($1\ \leq\ m\ \leq\ 500$), and the number of types of treasures $ k $ ($1\ \leq\ k\ \leq\ 100$).
• The following $ n $ lines contain the types of treasures buried at each position in the plaza.
• $ a_{i,j} $ ($1\ \leq\ a_{i,j}\ \leq\ k$) represents the type of treasure buried at position ($i,\ j$) in the plaza.
• The $n\ +\ 2$ line contains an integer $ q $ ($1\ \leq\ q\ \leq\ 100{,}000$) representing the number of queries.
• The following $ q $ lines contain information about each query.
• $ t_i $ ($1\ \leq\ t_i\ \leq\ 2$) represents the type of the $ i $-th query.
• When $t_i\ =\ 1$, it indicates that the $ i $-th query is a query where Jiro swaps the treasures at positions ($x_{1i},\ y_{1i}$) and ($x_{2i},\ y_{2i}$).
• When $t_i\ =\ 1$, it is guaranteed that ($x_{1i},\ y_{1i}$) and ($x_{2i},\ y_{2i}$) are adjacent.
• When $t_i\ =\ 2$, it indicates that the $ i $-th query is a query to investigate the current state of treasures within a rectangle parallel to the lines drawn in the plaza, with ($x_{1i},\ y_{1i}$) and ($x_{2i},\ y_{2i}$) as the diagonal vertices.
• When $t_i\ =\ 2$, it is guaranteed that $x_{1i}\ \leq\ x_{2i}$ and $y_{1i}\ \leq\ y_{2i}$.
• For each query, it is guaranteed that $1\ \leq\ x_{1i},\ x_{2i}\ \leq\ n$ and $1\ \leq\ y_{1i},\ y_{2i}\ \leq\ m$.

Output Format

For each query with $t_i\ =\ 2$, output the type and count of the most frequent treasure within the rectangle represented by the query in one line.

If there are multiple types of treasures with the highest frequency, output the one with the largest number representing the type of treasure.

End with a newline and do not include any extra characters or blank lines.

Sample Input and Output

Sample Input #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

Sample Output #1

2 3
1 3
3 2

Sample Input #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

Sample Output #2

1 1
2 2

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分