In una giornata di sole si è verificato un rapimento a un incrocio di una città. Si sospetta che i criminali siano Anna e Bruno, e che siano fuggiti dal luogo del rapimento in auto. L'auto non è stata ancora trovata. La polizia la sta cercando tuttora.

L'area urbana in cui i criminali stavano guidando l'auto è una città a griglia rettangolare con $H$ strade che corrono in direzione est-ovest e $W$ strade che corrono in direzione sud-nord. La distanza tra due incroci adiacenti è di 1 chilometro.

Ogni strada ha un intero associato, il grado di congestione. Il grado di congestione della $i$-esima strada ($1 \le i \le H$) da nord che corre in direzione est-ovest è $A_i$, mentre il grado di congestione della $j$-esima strada ($1 \le j \le W$) da ovest che corre in direzione sud-nord è $B_j$. Questi $H+W$ valori sono tutti diversi tra loro. Per ciascuna strada, il grado di congestione ha lo stesso valore in qualsiasi punto di essa.

Le indagini della polizia hanno rivelato che i criminali si sono mossi nella città nel modo seguente:

• Non sono usciti dalla città e non sono usciti dalle strade.
• All'inizio, i criminali hanno scelto una delle direzioni percorribili a partire dal luogo del rapimento e si sono mossi in quella direzione.
• Quando giungevano a un incrocio, se il grado di congestione della strada trasversale era maggiore di quello della strada attuale, svoltavano a quell'incrocio. Se era possibile svoltare in entrambe le direzioni, potevano scegliere una qualsiasi delle due.
• Quando giungevano a un incrocio, se il grado di congestione della strada attuale era maggiore di quello della strada trasversale, continuavano ad andare dritto. Tuttavia, se si trovavano sul confine della città e non potevano proseguire dritto, si fermavano in quel punto.

Ci sono $Q$ incroci candidati per il luogo del rapimento. Questi $Q$ candidati sono tutti diversi tra loro. Per determinare il numero di investigatori, la polizia vuole sapere, per ciascun incrocio candidato, la massima distanza di percorrenza possibile per i criminali supponendo che il rapimento sia avvenuto in quel luogo.

Per ciascuna delle $Q$ query, calcola la massima distanza di percorrenza possibile a partire dall'incrocio candidato fornito.

Compito

Dati i gradi di congestione delle strade della città e $Q$ incroci candidati per il luogo del rapimento, scrivi un programma che calcoli la massima distanza di percorrenza possibile da ciascun incrocio candidato.

Dati di ingresso

Leggi i seguenti dati dallo standard input.

• La prima riga di input contiene tre interi separati da spazio $H,W,Q$. Ciò significa che la città è una griglia rettangolare con $H$ strade che corrono in direzione est-ovest e $W$ strade che corrono in direzione sud-nord, e ci sono $Q$ incroci candidati per il luogo del rapimento.
• La seconda riga di input contiene $H$ interi separati da spazio $A_1,A_2,\ldots,A_H$. Ciò significa che il grado di congestione della $i$-esima strada ($1 \le i \le H$) da nord che corre in direzione est-ovest è $A_i$.
• La terza riga di input contiene $W$ interi separati da spazio $B_1,B_2,\ldots,B_W$. Ciò significa che il grado di congestione della $j$-esima strada ($1 \le j \le W$) da ovest che corre in direzione sud-nord è $B_j$.
• La $k$-esima riga ($1 \le k \le Q$) delle seguenti $Q$ righe contiene due interi separati da spazio $S_k,T_k$. Ciò significa che il $k$-esimo incrocio candidato per il luogo del rapimento è l'incrocio tra la $S_k$-esima strada da nord che corre in direzione est-ovest e la $T_k$-esima strada da ovest che corre in direzione sud-nord.

Dati di uscita

Scrivi $Q$ righe sullo standard output. La $k$-esima riga di output deve contenere un intero, la massima distanza di percorrenza possibile (in chilometri) a partire dal $k$-esimo incrocio candidato per il luogo del rapimento.

Assunzioni

Tutti i dati di ingresso soddisfano le seguenti condizioni.

• $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$).
• Gli $H+W$ interi $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ sono tutti diversi tra loro.
• $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$).

Subtask

Ci sono 5 subtask. Il punteggio e i vincoli aggiuntivi di ciascun subtask sono i seguenti:

Subtask 1 [13 punti]

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

Subtask 2 [10 punti]

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

Subtask 3 [17 punti]

• $Q=1$.

Subtask 4 [4 punti]

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

Subtask 5 [56 punti]

Non ci sono vincoli aggiuntivi.

Esempi

Input 1

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

Output 1

4
5
4
4
2

Nota

Ad esempio, per la terza query, la distanza di percorrenza raggiunge il valore massimo se i criminali si sono mossi nel modo seguente:

• Si sono mossi verso est per 1 chilometro dall'incrocio tra la seconda strada da nord e la seconda strada da ovest.
• Potevano muoversi verso sud o verso nord dall'incrocio tra la seconda strada da nord e la terza strada da ovest. Hanno scelto di muoversi verso sud per 1 chilometro.
• Potevano muoversi solo verso ovest dall'incrocio tra la terza strada da nord e la terza strada da ovest. Si sono mossi verso ovest per 1 chilometro.
• Potevano muoversi solo verso ovest dall'incrocio tra la terza strada da nord e la seconda strada da ovest. Si sono mossi verso ovest per 1 chilometro.
• Non potevano muoversi dall'incrocio tra la terza strada da nord e la prima strada da ovest. Si sono fermati in quel punto.

Se si sono mossi come descritto sopra, la distanza di percorrenza è di 4 chilometri.

Input 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

Output 2

7
6
9
4
6
9