某地的道路网可视为由 $H$ 条东西向道路与 $W$ 条南北向道路构成的网格，相邻的两条平行道路之间的距离为 $1\text{km}$。东西向道路从北到南依次编号为 $1\dots H$，南北向道路从西到东依次编号为 $1\dots W$ 。

东西向道路和南北向道路相交形成路口，规定 $x$ 号东西向街道和 $y$ 号南北向街道形成的路口的坐标是 $(x,y)$ 。

每条道路有一个车流指数。$i$ 号东西向道路 $(1\le i\le H)$ 的车流指数为 $A_i$，$j$ 号南北向道路 $(1\le j\le W)$ 的车流指数为 $B_j$。所有道路的车流指数互不相同。

给出 $Q$ 个互不相同的坐标 $(S_1,T_1),(S_2,T_2),\dots ,(S_Q,T_Q)$ 作为备选起点。对于每个备选起点，请计算：如果按照下述规则移动，最多可以移动多远。

• 移动开始时，可以任意选择方向。

• 当到达十字路口时：

  • 如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」小，就转弯。你可以选择左转还是右转。但如果你在城市边界上，可能只能左转/右转。
  • 如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」大，就直行。但如果前面没路（比如到了城市边界），就只能停在此处。
  • 不能掉头。

输入格式

第一行有三个整数 $H,W,Q$ ，用空格分隔。

第二行有 $H$ 个整数 $A_1\dots A_H$ ，用空格分隔。

第三行有 $W$ 个整数 $B_1\dots B_W$ ，用空格分隔。

在接下来的 $Q$ 行中，第 $k$ 行 $(1\le k\le Q)$ 有两个用空格分隔的整数 $S_k,T_k$。

输出格式

输出共 $Q$ 行，第 $i$ 行 $(1\le i\le Q)$ 有一个整数，表示以 $(S_i,T_i)$ 为起点，按照所给规则移动，最多可以移动多远。

样例一

input

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

output

4
5
4
4
2

explanation

例如，对于 $(S_3,T_3)=(2,2)$，最多可以移动 $4\text{km}$ 。

• 从 $(2,2)$ 向东移动 $1\text{km}$ ，到达 $(2,3)$ 。

• 在 $(2,3)$ 可以左转或右转。在 $(2,3)$ 左转，向南移动 $1\text{km}$ ，到达 $(3,3)$ 。

• 在 $(3,3)$ 只能右转。在 $(3,3)$ 右转，向西移动 $1\text{km}$ ，到达 $(3,2)$ 。

• 在 $(3,2)$ 只能直行。向西移动 $1\text{km}$ ，到达 $(3,1)$ 。

• 在 $(3,1)$ 无法移动。

样例二

input

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

output

7
6
9
4
6
9

数据范围与提示

$2\le H,W\le 5\times {10}^4,1\le Q\le 100,$ $1\le A_i,B_j\le {10}^9(1\le i\le H,1\le j\le W),$ $1\le S_k\le H,1\le T_k\le W(1\le k\le Q)$ 。

保证所有道路的车流指数互不相同，所有的备选起点互不相同。

时间限制：$5\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$