在一个阳光明媚的日子里，城市的一个十字路口发生了一起绑架事件。据怀疑，罪犯是 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$ 个候选点互不相同。为了确定调查人员的数量，警方希望知道，对于每个候选十字路口，假设绑架事件发生在该处，罪犯可能移动的最大距离是多少。

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

输入格式

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

• 第一行包含三个空格分隔的整数 $H, W, Q$。这表示城市是一个 $H$ 条东西向街道和 $W$ 条南北向街道组成的矩形网格，且有 $Q$ 个候选的案发现场十字路口。
• 第二行包含 $H$ 个空格分隔的整数 $A_1, A_2, \dots, A_H$。这表示从北向南数第 $i$ 条东西向街道（$1 \le i \le H$）的拥堵度为 $A_i$。
• 第三行包含 $W$ 个空格分隔的整数 $B_1, B_2, \dots, 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$ 个候选案发现场十字路口出发，罪犯可能移动的最大距离（单位：公里）。

数据范围

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

• $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, \dots, A_H, B_1, B_2, \dots, 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) \neq (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 2\,000, W \le 2\,000, Q = 1$。
• 子任务 3 [17 分]：$Q = 1$。
• 子任务 4 [4 分]：$H \le 2\,000, W \le 2\,000$。
• 子任务 5 [56 分]：无附加限制。

样例

样例输入 1

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

样例输出 1

4
5
4
4
2

样例输入 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

样例输出 2

7
6
9
4
6
9