B. Fruits
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are still a farmer. Now that you are tired of growing vegetables, you have decided to start growing fruits. Your farm has $$$N \cdot M$$$ fields arranged in $$$N$$$ rows numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ columns numbered from $$$1$$$ to $$$M$$$. The field at the $$$i$$$-th row and $$$j$$$-th column is denoted by $$$(i, j)$$$. Your farm grows $$$K$$$ distinct fruits, numbered from $$$1$$$ to $$$K$$$. Each field $$$(i, j)$$$ grows a single plant that bears the fruit $$$A_{i,j}$$$.

Your farm is home to many bees. A bee can move from a field $$$(i, j)$$$ to one of the fields $$$(i-1, j)$$$, $$$(i+1, j)$$$, $$$(i, j-1)$$$, or $$$(i, j+1)$$$ in one second (assuming that field exists). Bees carry pollen from one plant to other, which is critical for the production of fruits. Whenever a bee travels from some plant $$$(x_1, y_1)$$$ to some other plant $$$(x_2, y_2)$$$, it chooses a route such that it takes the smallest amount of time possible.

In order to study the effect of pollination in your farm as you choose which plants to grow, you would like to perform $$$Q$$$ operations numbered from $$$1$$$ from $$$Q$$$. Each operation is either type 1 or type 2.

Each operation $$$q$$$ (such that $$$1 \leq q \leq Q$$$) contains a number $$$T$$$, which specifies the type of the operation.

  • If $$$T = 1$$$, you are given a field $$$(I, J)$$$ and a fruit $$$X$$$, and asked to change the fruit produced by the field $$$(I, J)$$$ to $$$X$$$.
  • If $$$T = 2$$$, you are given two distinct fruits $$$U$$$ and $$$V$$$. Your task is to find a field $$$(x_1, y_1)$$$ that grows fruit $$$U$$$ and a field $$$(x_2, y_2)$$$ that grows fruit $$$V$$$ such that a bee carrying pollen from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$ will take the largest amount of time possible, and report this time in seconds. It is guaranteed that at any time, there will be at least one instance of each of the $$$K$$$ fruits.

Note that just before an operation of type 1, the field ($$$I, J$$$) could have been producing fruit $$$X$$$. That is, it is possible for no change to occur during an operation of type 1.

Input

The first line contains three space-separated integers $$$N$$$, $$$M$$$ and $$$K$$$, the number of rows in the farm, the number of columns in the farm, and the different fruits that can grow on the farm.

Each of the next $$$N$$$ lines contain $$$M$$$ space separated integers. The $$$i$$$-th of these lines contains $$$A_{i,1}, A_{i,2}, \cdots, A_{i,M}$$$, denoting the fruits growing at fields ($$$i, 1$$$), ($$$i, 2$$$), $$$\cdots$$$ ($$$i, M$$$).

The next line contains a single integer $$$Q$$$, denoting the number of operation.

The next $$$Q$$$ lines contain information about the operations. The $$$q$$$-th line describes the $$$q$$$-th operation. The first number in the line will be $$$T$$$, the type of the $$$q$$$-th operation.

  • If $$$T = 1$$$, the line will further contain three integers $$$I$$$, $$$J$$$ and $$$X$$$.
  • If $$$T = 2$$$, the line will further contain two integers $$$U$$$ and $$$V$$$.
Output

For each operation of type 2, output a single integer, the answer to the operation, on a new line.

Scoring

The test data for this problem is divided into multiple subtasks. In order to pass a subtask, your submitted program must solve every test case within that subtask correctly and within the time and memory limits.

You will be awarded the points allocated to a subtask if at least one submission you make during the contest passes that subtask. You do not need to combine your solutions for multiple subtasks into a single submission.

Please keep in mind that the subtasks are not necessarily arranged in increasing order of difficulty. We encourage you to try as many subtasks as possible.

Constraints

In all test data, it is guaranteed that:

  • $$$1 \leq N \leq 300\:000$$$
  • $$$1 \leq M \leq 300\:000$$$
  • $$$2 \leq N \cdot M \leq 300\:000$$$
  • $$$2 \leq K \leq N \cdot M$$$
  • $$$1 \leq A_{i,j} \leq K$$$ for all $$$1 \leq i \leq N$$$ and $$$1 \leq j \leq M$$$
  • $$$1 \leq Q \leq 200\:000$$$
  • For each $$$q$$$ such that $$$1 \leq q \leq Q$$$ :
    • $$$T = 1$$$ or $$$T = 2$$$.
    • If $$$T = 1$$$, then $$$1 \leq I \leq N$$$, $$$1 \leq J \leq M$$$, $$$1 \leq X \leq K$$$.
    • If $$$T = 2$$$, then $$$1 \leq U \leq K$$$, $$$1 \leq V \leq K$$$. Furthermore, $$$U \neq V$$$.
  • At any time, there will be at least one instance of each of the $$$K$$$ fruits.
  • There is at least one operation of type 2 in the input.

Subtasks

  • Subtask 1 (7 points) : $$$Q = 1, N \cdot M \leq 100$$$
  • Subtask 2 (8 points) : $$$Q = 1, N \cdot M \leq 500$$$.
  • Subtask 3 (13 points) : $$$Q = 1, N \cdot M \leq 2000$$$.
  • Subtask 4 (18 points) : $$$Q = 1$$$.
  • Subtask 5 (12 points) : $$$N = 1$$$ and there will be no operations of type 1.
  • Subtask 6 (9 points) : $$$N = 1$$$.
  • Subtask 7 (13 points) : $$$N \le 5$$$ and there will be no operations of type 1.
  • Subtask 8 (12 points) : There will be no operations of type 1.
  • Subtask 9 (8 points) : No additional constraints.
Examples
Input
5 5 9
7 1 5 5 4
2 4 6 2 8
7 1 3 5 6
9 4 4 8 2
1 3 6 9 3
1
2 1 3
Output
7
Input
4 3 12
8 9 1
3 10 12
2 5 11
4 6 7
7
2 1 6
2 6 9
2 2 11
1 3 3 11
2 5 8
2 8 2
2 2 11
Output
4
3
2
3
2
2
Input
1 9 4
2 1 1 1 3 4 2 3 3
6
2 1 2
2 3 2
2 1 3
2 2 4
2 4 1
2 3 4
Output
5
8
7
5
4
3
Input
1 13 7
6 4 3 4 5 1 7 7 1 6 7 2 4
5
2 7 3
2 3 4
1 1 2 3
2 4 7
2 4 3
Output
8
10
7
11
Input
7 7 20
9 17 15 17 18 20 11
7 12 13 18 12 16 18
3 18 6 8 5 10 16
7 11 5 17 2 2 1
8 11 4 12 3 2 12
19 2 7 13 3 6 14
6 8 8 15 9 20 17
6
2 17 8
2 1 12
2 6 14
2 17 1
2 18 8
2 2 8
Output
8
7
7
8
10
7
Note

Example 1

There is only one operation of type 2, with $$$U = 1$$$ and $$$V = 3$$$. The fields containing fruit $$$1$$$ are $$$(1, 2)$$$, $$$(3, 2)$$$, $$$(5, 1)$$$. Similarly, the fields containing fruit $$$3$$$ are $$$(3, 3)$$$, $$$(5, 2)$$$, $$$(5, 5)$$$.

In order to maximize the time taken by the bee, it is optimal to choose the fields $$$(1, 2)$$$ and $$$(5, 5)$$$. One possibility for the quickest path that a bee can take between these fields is: $$$(1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (4, 4) \rightarrow (4, 5) \rightarrow (5, 5)$$$. This path takes $$$7$$$ seconds, so the answer for this operation is $$$7$$$.

It is not possible to find a quicker path between $$$(1, 2)$$$ and $$$(5, 5)$$$. Further, if any other pair of fields is chosen, the quickest path between that pair will take time less than or equal to $$$7$$$ seconds.

Example 1 is valid for subtasks 1, 2, 3, 4, 7, 8 and 9.

Example 2 is valid for subtask 9.

Example 3 is valid for subtasks 5, 6, 7, 8 and 9.

Example 4 is valid for subtasks 6 and 9.

Example 5 is valid for subtasks 8 and 9.