납치 사건 2

맑은 날, 도시의 한 교차로에서 납치 사건이 일어났다. 경찰은 범인인 안나와 브루노가 차를 타고 현장을 빠져나간 것으로 보고 있다. 차는 아직 발견되지 않았고, 경찰은 지금도 차를 수색하고 있다.

이 도시는 동서 방향 도로 H개와 남북 방향 도로 W개로 이루어진 직사각형 격자다. 인접한 교차로 사이의 거리는 1킬로미터다.

각 도로에는 정수형 혼잡도가 있다. 북쪽에서 i번째 동서 방향 도로의 혼잡도는 $A_i$이고, 서쪽에서 j번째 남북 방향 도로의 혼잡도는 $B_j$이다. $H + W$개의 값은 모두 서로 다르다. 한 도로의 혼잡도는 도로 위 어느 지점에서나 같다.

경찰 조사로 범인들이 다음과 같이 이동했다는 사실이 드러났다.

• 범인들은 도시 밖으로 나가지 않았고, 도로를 벗어나지 않았다.
• 처음에 범인들은 현장에서 이동 가능한 방향 하나를 골라 그쪽으로 출발했다.
• 교차로에 이르렀을 때 교차하는 도로의 혼잡도가 현재 도로보다 크면, 그 교차로에서 방향을 틀었다. 양쪽 모두로 틀 수 있으면 둘 중 아무 쪽이나 고를 수 있었다.
• 교차로에 이르렀을 때 현재 도로의 혼잡도가 교차하는 도로보다 크면, 직진을 계속했다. 다만 도시 경계에 있고 직진할 수 없으면 그 자리에서 멈췄다.

현장 후보 교차로는 Q개이며 서로 다르다. 각 후보에 대해, 그 교차로에서 사건이 일어났다고 가정할 때 범인들이 이동할 수 있는 최대 거리를 구하라.

첫째 줄에 H, W, Q가 공백으로 구분되어 주어진다. 도시는 동서 방향 도로 H개와 남북 방향 도로 W개로 이루어진 격자이며, 현장 후보 교차로는 Q개다.

둘째 줄에 정수 $A_1, A_2, \ldots, A_H$가 H개 주어진다. $A_i$는 북쪽에서 i번째 동서 방향 도로의 혼잡도다.

셋째 줄에 정수 $B_1, B_2, \ldots, B_W$가 W개 주어진다. $B_j$는 서쪽에서 j번째 남북 방향 도로의 혼잡도다.

이어지는 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, \ldots, A_H, B_1, \ldots, B_W$는 서로 모두 다르다.
• $1 \le S_k \le H$, $1 \le T_k \le W$ ($1 \le k \le Q$)
• $k < l$인 모든 $k, l$에 대해 $(S_k, T_k) \ne (S_l, T_l)$이다.