【MX-X4-T5】「Jason-1」占领高地

有一张 $n$ 行 $m$ 列的地图，其第 $i$ 行 $j$ 列的位置的**高度**为 $h_{i,j}$ 且**军事化程度**为 $p_{i,j}$，且满足**任意两个四连通相邻的位置高度差的绝对值不超过 $\bm 1$**。 （两个位置 $(a, b)$、$(c, d)$ 四连通相邻，当且仅当 $\lvert a - c\rvert + \lvert b - d\rvert = 1$。） 你可以选择若干个位置建立补给站。若在位置 $(i,j)$ 建立了补给站，定义其**运输范围**为所有满足 $h_{i,j} - h_{x,y} + p_{i,j} \geq \lvert i - x\rvert + \lvert j - y\rvert$ 的位置 $(x, y)$。每个补给站都可以在其运输范围中任意移动物资的位置。 定义若干个补给站 $(x, y)$ 的安全程度为其中 $h_{x,y}$ 的最小值。 有 $q$ 次询问，每次给出四个整数 $a, b, c, d$，询问：若要建立若干个补给站，以将物资从位置 $(a, b)$ 运输至位置 $(c, d)$，则建立补给站的安全程度最大值是多少？或报告不可能完成运输任务。 **注意：物资可以通过多个补给站间接运输。不一定必须在 $(a, b)$ 和 $(c, d)$ 两点建立补给站。** **本题数据保证 $\bm{p_{i, j} \le 9}$。**

第一行，三个正整数 $n,m,q$，表示地图的行数、列数，和询问个数。 接下来 $n$ 行，每行 $m$ 个非负整数，其中第 $i$ 行第 $j$ 列的整数表示高度 $h_{i,j}$。**保证任意两个四连通相邻的位置高度差的绝对值不超过 $\bm 1$**。 接下来 $n$ 行，每行 $m$ 个非负整数，其中第 $i$ 行第 $j$ 列的整数表示军事化程度 $p_{i,j}$。**保证 $\bm{p_{i, j} \le 9}$**。 接下来 $q$ 行，每行四个正整数 $a, b, c, d$，表示询问。

$q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问的答案，即能让物资从 $(a,b)$ 运输至 $(c,d)$ 时，最大的安全程度。如果无论建立多少补给站都无法实现运输任务，则认为答案是 $-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

**【样例解释 #1】** 第一个询问可以在 $(1,3)$ 建立补给站，安全程度为 $3$。 第二个询问可以在 $(4,1)$ 建立补给站，安全程度为 $4$。 第三个询问可以在 $(3,2)$ 建立补给站，安全程度为 $3$。 第四个询问可以在 $(3,2)$ 建立补给站，安全程度为 $3$。 第五个询问可以在 $(4,1)$ 建立补给站，安全程度为 $4$。 第六个询问可以在 $(4,1),(1,3)$ 建立补给站，安全程度为 $3$。 **【样例解释 #2】** 仅有在 $(1,1)$ 建立的补给站可以将物资在 $(1,1)$、$(1,2)$ 间任意移动，在其它位置建立的补给站都将无法移动任何物资。 故仅有询问 $1$ 可以达成目标，只需在 $(1,1)$ 建立补给站，安全程度为 $1$。 **【数据范围】** **本题采用捆绑测试。** | 子任务 | $q \le$ | $n,m \le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $20$ | $10$ | A | $23$ | | 2 | $10^5$ | $300$ | B | $19$ | | 3 | $10^5$ | $100$ | 无 | $27$ | | 4 | $2 \times 10^5$ | $300$ | 无 | $31$ | - 特殊性质 A：$p_{i, j} \le 4$。 - 特殊性质 B：$p_{i, j} = 0$。 对于 $100 \%$ 的数据，$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)$，**保证任意两个四连通相邻的位置高度差的绝对值不超过 $\bm 1$**。