På en solrik dag skjedde det en kidnapping i et veikryss i en by. Det mistenkes at forbryterne var Anna og Bruno, og at de rømte fra åstedet i en bil. Bilen er ennå ikke funnet. Politiet leter fortsatt etter den.

Byområdet der forbryterne kjørte bilen er en by formet som et rektangulært rutenett med $H$ gater som går i øst-vest-retning og $W$ gater som går i sør-nord-retning. Avstanden mellom to nabokryss er 1 kilometer.

Hver gate har et heltall, trafikkbelastningsgraden. Trafikkbelastningsgraden til den $i$-te gaten ($1 \le i \le H$) fra nord som går i øst-vest-retning er $A_i$, og trafikkbelastningsgraden til den $j$-te gaten ($1 \le j \le W$) fra vest som går i sør-nord-retning er $B_j$. Disse $H+W$ verdiene er forskjellige fra hverandre. For hver gate har trafikkbelastningsgraden samme verdi ved alle punkter langs gaten.

Politiets etterforskning viste at forbryterne beveget seg i byen på følgende måte:

• De dro ikke ut av byen, og de forlot ikke gatene.
• Til å begynne med valgte forbryterne én av de mulige kjøreretningene fra åstedet, og kjørte i den retningen.
• Når de kom til et kryss, svingte de i krysset hvis trafikkbelastningsgraden til den kryssende gaten var større enn på den nåværende gaten. Hvis det var mulig å svinge i begge retninger, kunne de velge hvilken som helst av dem.
• Når de kom til et kryss, fortsatte de rett frem hvis trafikkbelastningsgraden til den nåværende gaten var større enn på den kryssende gaten. Men hvis de var ved bygrensen og ikke kunne kjøre rett frem, stoppet de på det stedet.

Det er $Q$ kandidatkryss for åstedet for kidnappingen. Disse $Q$ kandidatene er forskjellige fra hverandre. For å bestemme antallet etterforskere ønsker politiet å vite, for hvert kandidatkryss, den maksimalt mulige kjørelengden for forbryterne forutsatt at kidnappingen skjedde på det stedet.

For hver av de $Q$ spørringene, beregn den maksimalt mulige kjørelengden fra det gitte kandidatkrysset.

Oppgave

Gitt trafikkbelastningsgradene til gatene i byen og $Q$ kandidatkryss for åstedet, skriv et program som beregner den maksimalt mulige kjørelengden fra hvert kandidatkryss.

Inndata

Les følgende data fra standard inndata.

• Den første linjen i inndataene inneholder tre mellomromseparerte heltall $H,W,Q$. Dette betyr at byen er et rektangulært rutenett med $H$ gater som går i øst-vest-retning og $W$ gater som går i sør-nord-retning, og at det er $Q$ kandidatkryss for åstedet.
• Den andre linjen i inndataene inneholder $H$ mellomromseparerte heltall $A_1,A_2,\ldots,A_H$. Dette betyr at trafikkbelastningsgraden til den $i$-te gaten ($1 \le i \le H$) fra nord som går i øst-vest-retning er $A_i$.
• Den tredje linjen i inndataene inneholder $W$ mellomromseparerte heltall $B_1,B_2,\ldots,B_W$. Dette betyr at trafikkbelastningsgraden til den $j$-te gaten ($1 \le j \le W$) fra vest som går i sør-nord-retning er $B_j$.
• Den $k$-te linjen ($1 \le k \le Q$) av de følgende $Q$ linjene inneholder to mellomromseparerte heltall $S_k,T_k$. Dette betyr at det $k$-te kandidatkrysset for åstedet er krysset mellom den $S_k$-te gaten fra nord som går i øst-vest-retning og den $T_k$-te gaten fra vest som går i sør-nord-retning.

Utdata

Skriv $Q$ linjer til standard utdata. Den $k$-te linjen i utdataene skal inneholde et heltall, den maksimalt mulige kjørelengden (i kilometer) fra det $k$-te kandidatkrysset for åstedet.

Begrensninger

Alle inndata oppfyller følgende betingelser.

• $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$).
• De $H+W$ heltallene $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ er forskjellige fra hverandre.
• $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$).

Deloppgaver

Det er 5 deloppgaver. Poengsummen og tilleggsbegrensningene for hver deloppgave er som følger:

Deloppgave 1 [13 poeng]

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

Deloppgave 2 [10 poeng]

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

Deloppgave 3 [17 poeng]

• $Q=1$.

Deloppgave 4 [4 poeng]

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

Deloppgave 5 [56 poeng]

Det er ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

4
5
4
4
2

Merk

For eksempel, for den tredje spørringen oppnår kjørelengden maksimalverdien hvis forbryterne beveget seg på følgende måte:

• De kjørte østover i 1 kilometer fra krysset mellom den andre gaten fra nord og den andre gaten fra vest.
• De kunne kjøre sørover eller nordover fra krysset mellom den andre gaten fra nord og den tredje gaten fra vest. De valgte å kjøre sørover i 1 kilometer.
• De kunne kun kjøre vestover fra krysset mellom den tredje gaten fra nord og den tredje gaten fra vest. De kjørte vestover i 1 kilometer.
• De kunne kun kjøre vestover fra krysset mellom den tredje gaten fra nord og den andre gaten fra vest. De kjørte vestover i 1 kilometer.
• De kunne ikke kjøre videre fra krysset mellom den tredje gaten fra nord og den første gaten fra vest. De stoppet på det stedet.

Hvis de beveget seg som beskrevet ovenfor, er kjørelengden 4 kilometer.

Inndata 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

Utdata 2

7
6
9
4
6
9