Define $f(A)$ as the result obtained after performing the following operations on matrix $A$:

1. Independently sort each row of matrix $A$ such that the elements in each row are monotonically non-decreasing from left to right. If the matrix after sorting is identical to the matrix before sorting, the transformation stops; otherwise, proceed to the operation described in 2.
2. Independently sort each column of matrix $A$ such that the elements in each column are monotonically non-decreasing from top to bottom. If the matrix after sorting is identical to the matrix before sorting, the transformation stops; otherwise, proceed to the operation described in 1.

Given an $n \times m$ integer matrix $P$, where $1 \le P_{ij} \le n \times m$ and all elements in the matrix are distinct.

There are $q$ operations of the following two types:

• Modification: Given two positions $(x_1, y_1)$ and $(x_2, y_2)$ in the matrix, swap the elements at these two positions, i.e., swap $P_{x_1y_1}$ and $P_{x_2y_2}$.
• Query: Given a position $(x, y)$ in the matrix, output the element at that position in matrix $f(P)$, i.e., $f(P)_{xy}$. Note that the query operation does not actually change the state of the matrix.

Input

Read data from standard input.

The first line contains three integers $n, m, q$ ($1 \le n \times m \le 2 \times 10^5$, $1 \le q \le 2 \times 10^5$).

The next $n$ lines each contain $m$ integers, describing the elements of matrix $P$ row by row. It is guaranteed that these elements are all between $1$ and $n \times m$ and are distinct.

The next $q$ lines each start with an integer $opt \in \{1, 2\}$, representing the operation type.

• If $opt = 1$, it represents a modification operation. Then read four integers $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2 \le n, 1 \le y_1, y_2 \le m$), representing the swap of $P_{x_1y_1}$ and $P_{x_2y_2}$.
• If $opt = 2$, it represents a query operation. Then read two integers $x, y$ ($1 \le x \le n, 1 \le y \le m$), representing the query for the value of $f(P)_{xy}$.

Output

Output to standard output. For each query operation, output the value of the corresponding element.

Examples

Input 1

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

Output 1

4
3
3
4
1
2

Note

For the first query, the matrix is:

1 4
2 3

We find that sorting by rows does not change the matrix, so the answer is the element in the first row and second column, which is 4.

For the second query, the matrix is:

1 4
2 3

We first sort by rows, resulting in:

1 4
2 3

Then we sort by columns, resulting in:

1 3
2 4

We then attempt to sort by rows again and find that the matrix does not change. Therefore, the answer is the element in the first row and second column at this time, which is 3.