You are a farmer, and you want to grow a wide variety of vegetables so that the people in your town can eat a balanced diet.
In order to remain healthy, a person must eat a diet that contains $$$N$$$ essential vegetables, numbered from $$$1$$$ to $$$N$$$. In total, your town requires $$$A_i$$$ units of each vegetable $$$i$$$, for $$$1 \leq i \leq N$$$. In order to grow a single unit of vegetable $$$i$$$, you require $$$B_i$$$ units of water.
However, you can use upgrades to improve the efficiency of your farm. In a single upgrade, you can do one of the following two actions:
- You can improve the nutritional value of your produce so that your town requires one less unit of some vegetable $$$i$$$. Specifically, you can choose any one vegetable $$$i$$$ such that $$$A_i \geq 1$$$, and reduce $$$A_i$$$ by $$$1$$$.
- You can improve the quality of your soil so that growing one unit of some vegetable $$$i$$$ requires one less unit of water. Specifically, you can choose any one vegetable $$$i$$$ such that $$$B_i \geq 1$$$, and reduce $$$B_i$$$ by $$$1$$$.
You wish to answer $$$Q$$$ questions numbered from $$$1$$$ to $$$Q$$$, where the $$$j$$$-th question is the following:
- If you use at most $$$X_j$$$ upgrades, what is the minimum possible number of units of water you will need to feed your town?
The first line contains two space-separated integers $$$N$$$ and $$$Q$$$, the number of essential vegetables and the number of questions, respectively.
The second line contains $$$N$$$ space separated integers, $$$A_1$$$, $$$A_2$$$, $$$...$$$ $$$A_N$$$.
The third line contains $$$N$$$ space separated integers, $$$B_1$$$, $$$B_2$$$, $$$...$$$ $$$B_N$$$.
The following $$$Q$$$ lines describe the questions. The $$$j$$$-th of these lines contains a single integer $$$X_j$$$.
You should print $$$Q$$$ lines of output. The $$$j$$$-th line should be the answer to the $$$j$$$-th question.
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 2 \cdot 10^5$$$.
- $$$1 \leq Q \leq 2 \cdot 10^5$$$.
- $$$1 \leq A_i \leq 10^6$$$ for all $$$1 \leq i \leq N$$$.
- $$$1 \leq B_i \leq 10^6$$$ for all $$$1 \leq i \leq N$$$.
- $$$1 \leq X_j \leq 10^9$$$ for all $$$1 \leq j \leq Q$$$.
Please be aware that the output for this problem may not fit in 32-bit integers. You may need to use 64-bit integers in your computations.
Subtasks
- Subtask 1 (7 points) $$$Q = 1$$$, $$$X_j = 1$$$, $$$N \leq 10$$$, $$$A_i \leq 10^3$$$, $$$B_i \leq 10^3$$$.
- Subtask 2 (6 points) $$$Q \leq 3$$$, $$$X_j \leq 3$$$, $$$N \leq 10$$$.
- Subtask 3 (9 points) $$$A_i = 1$$$, $$$N \leq 10^3$$$, $$$Q \leq 10^3$$$.
- Subtask 4 (7 points) $$$A_i = 1$$$.
- Subtask 5 (18 points) $$$N, Q, X_j \leq 30$$$.
- Subtask 6 (15 points) $$$N, Q, X_j \leq 400$$$.
- Subtask 7 (16 points) $$$N, Q \leq 10^3$$$.
- Subtask 8 (7 points) The sum of all $$$A_i$$$ does not exceed $$$2 \cdot 10^5$$$. Also, the sum of all $$$B_i$$$ does not exceed $$$2 \cdot 10^5$$$.
- Subtask 9 (7 points) $$$X_j \leq 2 \cdot 10^5$$$.
- Subtask 10 (8 points) No additional constraints.
4 22 4 5 35 2 3 312
37 32
4 11 4 2 35 4 3 629
0
14 41 1 1 1 1 1 1 1 1 1 1 1 1 14 2 4 12 10 5 2 6 4 10 2 3 5 123956
47 13 31 26
8 67 9 4 2 2 2 7 71 10 6 7 4 6 8 42931227819
8 209 125 20 159 72
1 1100000010000001
999999000000
In example 1, there are two operations.
- For the first query, $$$X_1 = 1$$$ so you are allowed up to $$$1$$$ upgrade. One optimal choice is to reduce $$$A_1$$$ by $$$1$$$. Then, the final array $$$A$$$ is $$$[1, 4, 5, 3]$$$ and the final array $$$B$$$ is $$$[5, 2, 3, 3]$$$. This yields a water requirement of $$$37$$$ units.
- For the second query, $$$X_2 = 2$$$ so you are allowed up to $$$2$$$ upgrades. One optimal choice is to reduce $$$A_1$$$ by $$$1$$$ and reduce $$$B_3$$$ by $$$1$$$. Then, the final array $$$A$$$ is $$$[1, 4, 5, 3]$$$ and the final array $$$B$$$ is $$$[5, 2, 2, 3]$$$. This yields a water requirement of $$$32$$$ units.
Example 1 is valid for subtasks 2, 5, 6, 7, 8, 9 and 10.
In example 2, there is only one operation. You are allowed up to $$$29$$$ upgrades, which is sufficient to make the final array $$$A$$$ and the final array $$$B$$$ both $$$[0, 0, 0, 0]$$$. This yields a water requirement of $$$0$$$ units.
Example 2 is valid for subtasks 5, 6, 7, 8, 9 and 10.
Example 3 is valid for subtasks 3, 4, 5, 6, 7, 8, 9 and 10.
Example 4 is valid for subtasks 5, 6, 7, 8, 9 and 10.
Example 5 is valid for subtasks 2, 5, 6, 7, 8, 9 and 10.
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.
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$$$.
For each operation of type 2, output a single integer, the answer to the operation, on a new line.
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.
5 5 97 1 5 5 42 4 6 2 87 1 3 5 69 4 4 8 21 3 6 9 312 1 3
7
4 3 128 9 13 10 122 5 114 6 772 1 62 6 92 2 111 3 3 112 5 82 8 22 2 11
4 3 2 3 2 2
1 9 42 1 1 1 3 4 2 3 362 1 22 3 22 1 32 2 42 4 12 3 4
5 8 7 5 4 3
1 13 76 4 3 4 5 1 7 7 1 6 7 2 452 7 32 3 41 1 2 32 4 72 4 3
8 10 7 11
7 7 209 17 15 17 18 20 117 12 13 18 12 16 183 18 6 8 5 10 167 11 5 17 2 2 18 11 4 12 3 2 1219 2 7 13 3 6 146 8 8 15 9 20 1762 17 82 1 122 6 142 17 12 18 82 2 8
8 7 7 8 10 7
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.