Un día soleado se produjo un secuestro en un cruce de una ciudad. Se sospecha que los delincuentes eran Anna y Bruno, quienes huyeron del lugar del secuestro en coche. El coche todavía no ha sido encontrado y la policía sigue buscándolo.

La zona urbana por la que circulaban los delincuentes tiene forma de cuadrícula rectangular, con $H$ calles en dirección este-oeste y $W$ calles en dirección sur-norte. La distancia entre dos cruces adyacentes es de $1$ kilómetro.

Cada calle tiene un número entero llamado grado de congestión. El grado de congestión de la calle este-oeste número $i$ contando desde el norte ($1 \le i \le H$) es $A_i$, y el de la calle sur-norte número $j$ contando desde el oeste ($1 \le j \le W$) es $B_j$. Estos $H+W$ valores son todos distintos. En cada calle, el grado de congestión es el mismo en todos sus puntos.

La investigación policial reveló que los delincuentes se desplazaron por la ciudad de la siguiente manera:

• No salieron de la ciudad ni abandonaron las calles.
• Al principio, eligieron una de las direcciones en las que podían moverse desde el lugar del secuestro y avanzaron en esa dirección.
• Al llegar a un cruce, si el grado de congestión de la calle transversal era mayor que el de la calle por la que circulaban, giraban en ese cruce. Si podían girar en ambos sentidos, podían elegir cualquiera de ellos.
• Al llegar a un cruce, si el grado de congestión de la calle por la que circulaban era mayor que el de la calle transversal, seguían recto. Sin embargo, si estaban en el límite de la ciudad y no podían seguir recto, se detenían en ese lugar.

Hay $Q$ cruces candidatos a ser el lugar del secuestro, todos distintos. Para determinar el número de investigadores, la policía quiere conocer, para cada cruce candidato, la máxima distancia que podrían haber recorrido los delincuentes suponiendo que el secuestro hubiera ocurrido allí.

Para cada una de las $Q$ consultas, calcula la máxima distancia que podrían haber recorrido desde el cruce candidato dado.

Tarea

Dados los grados de congestión de las calles de la ciudad y los $Q$ cruces candidatos a ser el lugar del secuestro, escribe un programa que calcule la máxima distancia que podrían haber recorrido desde cada cruce candidato.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene tres enteros $H,W,Q$, separados por espacios. La ciudad es una cuadrícula rectangular con $H$ calles en dirección este-oeste y $W$ calles en dirección sur-norte, y hay $Q$ cruces candidatos a ser el lugar del secuestro.
• La segunda línea contiene $H$ enteros $A_1,A_2,\ldots,A_H$, separados por espacios. El grado de congestión de la calle este-oeste número $i$ contando desde el norte ($1 \le i \le H$) es $A_i$.
• La tercera línea contiene $W$ enteros $B_1,B_2,\ldots,B_W$, separados por espacios. El grado de congestión de la calle sur-norte número $j$ contando desde el oeste ($1 \le j \le W$) es $B_j$.
• La línea $k$ ($1 \le k \le Q$) de las siguientes $Q$ líneas contiene dos enteros $S_k,T_k$, separados por espacios. El cruce candidato número $k$ es la intersección de la calle este-oeste número $S_k$ contando desde el norte y la calle sur-norte número $T_k$ contando desde el oeste.

Salida

Escribe $Q$ líneas en la salida estándar. La línea $k$ debe contener un entero: la máxima distancia posible recorrida (en kilómetros) desde el cruce candidato número $k$.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $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$).
• Los $H+W$ enteros $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ son todos distintos.
• $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$).

Subtareas

Hay 5 subtareas. La puntuación y las restricciones adicionales de cada una son las siguientes:

Subtarea 1 [13 puntos]

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

Subtarea 2 [10 puntos]

• $H \le 2\,000$.
• $W \le 2\,000$.
• $Q=1$.

Subtarea 3 [17 puntos]

• $Q=1$.

Subtarea 4 [4 puntos]

• $H \le 2\,000$.
• $W \le 2\,000$.

Subtarea 5 [56 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

4
5
4
4
2

Nota

Por ejemplo, para la tercera consulta, se alcanza la máxima distancia recorrida si los delincuentes se desplazan de la siguiente manera:

• Avanzan $1$ kilómetro hacia el este desde la intersección de la segunda calle contando desde el norte y la segunda calle contando desde el oeste.
• Desde la intersección de la segunda calle contando desde el norte y la tercera calle contando desde el oeste pueden ir hacia el sur o hacia el norte. Eligen avanzar $1$ kilómetro hacia el sur.
• Desde la intersección de la tercera calle contando desde el norte y la tercera calle contando desde el oeste solo pueden ir hacia el oeste. Avanzan $1$ kilómetro hacia el oeste.
• Desde la intersección de la tercera calle contando desde el norte y la segunda calle contando desde el oeste solo pueden ir hacia el oeste. Avanzan $1$ kilómetro hacia el oeste.
• No pueden moverse desde la intersección de la tercera calle contando desde el norte y la primera calle contando desde el oeste. Se detienen en ese lugar.

Si se desplazan de esta manera, la distancia recorrida es de $4$ kilómetros.

Entrada 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

Salida 2

7
6
9
4
6
9