题目描述

有一张 $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		$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$。