题目描述

在一个晴朗的白天，城市的一个十字路口发生了一起绑架事件。警方怀疑罪犯是 Anna 和 Bruno，他们作案后驾车逃离现场。目前，涉案车辆尚未被找到，警方仍在搜寻中。

罪犯驾车所经过的城区是一个矩形网格城市，包含 $H$ 条东西走向的街道和 $W$ 条南北走向的街道。相邻两个十字路口之间的距离为 1 公里。

每条街道都有一个整数，称为“拥堵度”。第 $i$ 条东西走向的街道（$1 \le i \le H$）的拥堵度为 $A_i$，第 $j$ 条南北走向的街道（$1 \le j \le W$）的拥堵度为 $B_j$。这 $H + W$ 个拥堵度值互不相同。对于每条街道，其拥堵度在整条街道上的任意位置均保持不变。

警方调查发现，罪犯在城市中的移动方式如下：

• 他们未离开城市，也未偏离街道。
• 起初，罪犯从绑架现场选择一个可移动的方向，并朝该方向前进。
• 当他们到达一个十字路口时，若横向街道的拥堵度大于当前街道的拥堵度，他们会在该路口转弯。若可向两个方向转弯，他们可任选其一。
• 当他们到达一个十字路口时，若当前街道的拥堵度大于横向街道的拥堵度，他们将继续直行。然而，若他们位于城市边界且无法继续直行，则会在该处停止移动。

共有 $Q$ 个候选十字路口作为绑架现场。这 $Q$ 个候选地点互不相同。为了确定所需调查员人数，警方希望知道：对于每个候选十字路口，假设绑架事件发生在该处，罪犯可能行驶的最大距离是多少。

对于每个 $Q$ 个查询，请计算从给定候选十字路口出发，罪犯可能行驶的最大距离。

任务

给定城市中各街道的拥堵度以及 $Q$ 个绑架现场的候选十字路口，编写一个程序，计算从每个候选十字路口出发，罪犯可能行驶的最大距离。

输入格式

从标准输入读取以下数据：

• 第一行包含三个以空格分隔的整数 $H$、$W$、$Q$。这表示城市是一个矩形网格，包含 $H$ 条东西走向的街道和 $W$ 条南北走向的街道，且共有 $Q$ 个绑架现场的候选十字路口。
• 第二行包含 $H$ 个以空格分隔的整数 $A_1, A_2, \ldots, A_H$。这表示第 $i$ 条（$1 \le i \le H$）从北往南数的东西走向街道的拥堵度为 $A_i$。
• 第三行包含 $W$ 个以空格分隔的整数 $B_1, B_2, \ldots, B_W$。这表示第 $j$ 条（$1 \le j \le W$）从西往东数的南北走向街道的拥堵度为 $B_j$。
• 接下来的 $Q$ 行中，第 $k$ 行（$1 \le k \le Q$）包含两个以空格分隔的整数 $S_k$、$T_k$。这表示第 $k$ 个绑架现场的候选十字路口位于第 $S_k$ 条从北往南数的东西走向街道与第 $T_k$ 条从西往东数的南北走向街道的交汇处。

输出格式

向标准输出写入 $Q$ 行。第 $k$ 行应包含一个整数，表示从第 $k$ 个候选十字路口出发，罪犯可能行驶的最大距离（单位：公里）。

3 3 5
3 2 6
1 4 5
1 1
1 2
2 2
3 1
3 3

4
5
4
4
2

4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3

7
6
9
4
6
9

提示

样例 1 解释

例如，对于第三个查询，若罪犯按以下方式移动，则行驶距离可达到最大值：

• 他们从从北数第二条街道与从西数第二条街道的交叉口向东移动 1 公里。
• 他们可以从从北数第二条街道与从西数第三条街道的交叉口向南或向北移动，他们选择向南移动 1 公里。
• 他们只能从从北数第三条街道与从西数第三条街道的交叉口向西移动，他们向西移动了 1 公里。
• 他们只能从从北数第三条街道与从西数第二条街道的交叉口向西移动，他们向西移动了 1 公里。
• 他们无法从从北数第三条街道与从西数第一条街道的交叉口继续移动，因此在该处停止。

若他们按上述方式移动，总行驶距离为 4 公里。

数据范围

所有输入数据满足以下条件：

• $2 \le H \le 50\,000$。
• $2 \le W \le 50\,000$。
• $1 \le Q \le 100$。
• $1 \le A_i \le 1\,000\,000\,000$（$1 \le i \le H$）。
• $1 \le B_j \le 1\,000\,000\,000$（$1 \le j \le W$）。
• $H + W$ 个整数 $A_1, A_2, \ldots, A_H, B_1, B_2, \ldots, B_W$ 互不相同。
• $1 \le S_k \le H$（$1 \le k \le Q$）。
• $1 \le T_k \le W$（$1 \le k \le Q$）。
• $(S_k, T_k) \ne (S_l, T_l)$（$1 \le k < l \le Q$）。

子任务

共有 5 个子任务。每个子任务的得分及附加限制如下：

子任务 1 [13 分]

• $H \le 8$。
• $W \le 8$。
• $Q = 1$。

子任务 2 [10 分]

• $H \le 2000$。
• $W \le 2000$。
• $Q = 1$。

子任务 3 [17 分]

• $Q = 1$。

子任务 4 [4 分]

• $H \le 2000$。
• $W \le 2000$。

子任务 5 [56 分]

无附加限制。

翻译由 Qwen3-235B 完成