Matrix Row-Column Sort Transformation

Define \(f(A)\) as the result of applying the following operations on a matrix \(A\):

1. Sort each row of \(A\) independently so that the elements in each row are in non-decreasing order from left to right. If the sorted matrix is identical to \(A\), the transformation stops; otherwise, proceed to step 2.
2. Sort each column of \(A\) independently so that the elements in each column are in non-decreasing order from top to bottom. If the sorted matrix is identical to \(A\), the transformation stops; otherwise, return to step 1.

We are given an \(n \times m\) integer matrix \(P\) with distinct elements satisfying \(1 \le P_{ij} \le n\times m\). You will then perform \(q\) operations on matrix \(P\). The operations are of two types:

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

Observation: Since \(P\) is always a permutation of \(\{1,2,\dots, n\times m\}\), the final matrix \(f(P)\) is uniquely determined. In fact, after applying the transformations, the matrix will become:

\[ f(P)_{ij} = (i-1) \times m + j, \quad \text{for } 1 \le i \le n,\ 1 \le j \le m. \]

Your task is to process the operations and answer the queries accordingly.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) where \(1 \le n, m \le 10^5\) (with \(n \times m\) within practical limits) and \(q\) is the number of operations.

The next \(n\) lines each contain \(m\) integers representing the matrix \(P\). It is guaranteed that \(P\) is a permutation of \(\{1,2,\dots, n\times m\}\).

The following \(q\) lines describe the operations. Each operation is in one of the following formats:

• For a modification operation: 1 x1 y1 x2 y2
• For a query operation: 2 x y

All indices are 1-indexed.

outputFormat

For each query operation, output a single line containing the answer \(f(P)_{xy}\) corresponding to the given position.

The final matrix \(f(P)\) is the doubly sorted matrix where:

\[ f(P)_{ij} = (i-1) \times m + j, \quad 1\le i \le n,\ 1 \le j \le m. \]</p>

sample

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

1
4

</p>