Background

Original link: https://oier.team/problems/X4F.

Problem Description

There is a map with $n$ rows and $m$ columns. The height of the cell in row $i$, column $j$ is $h_{i,j}$, and its militarization level is $p_{i,j}$. It satisfies that for any two 4-directionally adjacent cells, the absolute difference of their heights is at most $\bm 1$.
(Two cells $(a, b)$ and $(c, d)$ are 4-directionally adjacent if and only if $\lvert a - c\rvert + \lvert b - d\rvert = 1$.)

You may choose several cells to build supply stations. If a supply station is built at cell $(i, j)$, define its transport range as all cells $(x, y)$ satisfying $h_{i,j} - h_{x,y} + p_{i,j} \geq \lvert i - x\rvert + \lvert j - y\rvert$. Each supply station can move supplies between any cells within its transport range.

Define the security level of several supply stations $(x, y)$ as the minimum value among their $h_{x,y}$.

There are $q$ queries. Each query gives four integers $a, b, c, d$ and asks: if you want to build some supply stations to transport supplies from cell $(a, b)$ to cell $(c, d)$, what is the maximum possible security level of the stations you build? Or report that it is impossible to complete the transport task.

Note: supplies can be transported indirectly through multiple supply stations. It is not necessary to build stations at $(a, b)$ and $(c, d)$.

This problem guarantees $\bm{p_{i, j} \le 9}$.

Input Format

The first line contains three positive integers $n, m, q$, representing the number of rows, the number of columns, and the number of queries.

The next $n$ lines each contain $m$ non-negative integers. The integer in row $i$, column $j$ represents the height $h_{i,j}$. It is guaranteed that for any two 4-directionally adjacent cells, the absolute difference of their heights is at most $\bm 1$.

The next $n$ lines each contain $m$ non-negative integers. The integer in row $i$, column $j$ represents the militarization level $p_{i,j}$. It is guaranteed that $\bm{p_{i, j} \le 9}$.

The next $q$ lines each contain four positive integers $a, b, c, d$, representing a query.

Output Format

Output $q$ lines. The $i$-th line contains one integer, representing the answer to the $i$-th query, i.e. the maximum security level that allows supplies to be transported from $(a, b)$ to $(c, d)$. If the transport task cannot be completed no matter how many supply stations are built, output $-1$.

4 4 6
1 2 3 2
2 3 2 3
3 3 2 2
4 3 2 1
2 1 1 1
0 1 1 0
1 1 0 1
0 0 1 2
1 1 1 2
1 1 2 1
2 2 4 4
2 3 3 1
4 4 2 1
1 4 4 1

3
4
3
3
4
3

1 3 3
1 1 1
1 0 0
1 1 1 2
1 1 1 3
1 2 1 3

1
-1
-1

8 8 10
5 6 6 5 6 7 8 9
5 6 6 5 6 6 7 8
4 5 5 4 5 5 6 7
3 4 5 4 5 6 6 7
4 5 5 5 5 6 7 6
5 4 5 5 4 5 6 7
4 3 4 5 4 5 6 6
5 4 4 4 3 4 5 5
0 0 0 0 1 0 2 0
0 0 0 0 0 0 0 0
0 1 0 2 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
6 3 7 7
1 5 2 2
7 7 6 7
4 3 7 7
7 6 8 2
3 2 8 7
1 6 8 6
1 6 7 4
4 5 4 4
5 4 1 1

5
5
6
5
5
5
6
5
8
-1

Hint

[Sample Explanation #1]

For the first query, you can build a supply station at $(1, 3)$, and the security level is $3$.

For the second query, you can build a supply station at $(4, 1)$, and the security level is $4$.

For the third query, you can build a supply station at $(3, 2)$, and the security level is $3$.

For the fourth query, you can build a supply station at $(3, 2)$, and the security level is $3$.

For the fifth query, you can build a supply station at $(4, 1)$, and the security level is $4$.

For the sixth query, you can build supply stations at $(4, 1)$ and $(1, 3)$, and the security level is $3$.

[Sample Explanation #2]

Only a supply station built at $(1, 1)$ can move supplies freely between $(1, 1)$ and $(1, 2)$. A supply station built at any other cell will not be able to move any supplies.

Therefore, only query $1$ can be achieved. You only need to build a supply station at $(1, 1)$, and the security level is $1$.

[Constraints]

This problem uses bundled testdata.

• Special property A: $p_{i, j} \le 4$.
• Special property B: $p_{i, j} = 0$.

For $100\%$ of the testdata, $1 \le n, m \le 300$, $0 \le h_{i,j} \le 10^9$, $\bm{0 \le p_{i,j} \le 9}$, $1 \le q \le 2 \times 10^5$, $1 \le a, c \le n$, $1 \le b, d \le m$, $(a, b) \neq (c, d)$, and it is guaranteed that for any two 4-directionally adjacent cells, the absolute difference of their heights is at most $\bm 1$.

Translated by ChatGPT 5