En solig dag inträffade en kidnappning vid en korsning i en stad. Det misstänks att brottslingarna var Anna och Bruno, och att de flydde från kidnappningsplatsen i en bil. Bilen har ännu inte hittats. Polisen letar efter den än idag.

Stadsområdet där brottslingarna körde bilen är en stad med ett rektangulärt rutnät med $H$ gator som går i öst-västlig riktning och $W$ gator som går i syd-nordlig riktning. Avståndet mellan två intilliggande korsningar är 1 kilometer.

Varje gata har ett heltal, trängselgraden. Trängselgraden för den $i$-te gatan ($1 \le i \le H$) från norr som går i öst-västlig riktning är $A_i$, och trängselgraden för den $j$-te gatan ($1 \le j \le W$) från väster som går i syd-nordlig riktning är $B_j$. Dessa $H+W$ värden är alla olika. För varje gata har trängselgraden samma värde vid alla punkter längs den.

Polisens utredning visade att brottslingarna rörde sig i staden på följande sätt:

• De åkte inte ut ur staden, och de åkte inte utanför gatorna.
• I början valde brottslingarna en av de möjliga färdriktningarna från kidnappningsplatsen och åkte i den riktningen.
• När de kom till en korsning svängde de i korsningen om trängselgraden på den korsande gatan var större än på den nuvarande gatan. Om det var möjligt att svänga åt båda hållen kunde de välja vilket som helst av dem.
• När de kom till en korsning fortsatte de rakt fram om trängselgraden på den nuvarande gatan var större än på den korsande gatan. Men om de befann sig vid stadens gräns och inte kunde fortsätta rakt fram stannade de på den platsen.

Det finns $Q$ kandidatkorsningar för kidnappningsplatsen. Dessa $Q$ kandidater är alla olika. För att bestämma antalet utredare vill polisen för varje kandidatkorsning veta den maximalt möjliga körsträckan för brottslingarna under antagandet att kidnappningen ägde rum på den platsen.

Beräkna för var och en av de $Q$ frågorna den maximalt möjliga körsträckan från den givna kandidatkorsningen.

Uppgift

Givet trängselgraderna för gatorna i staden och $Q$ kandidatkorsningar för kidnappningsplatsen, skriv ett program som beräknar den maximalt möjliga körsträckan från varje kandidatkorsning.

Indata

Läs följande data från standard inmatning.

• Den första raden i indatan innehåller tre mellanslagsseparerade heltal $H,W,Q$. Detta betyder att staden är ett rektangulärt rutnät med $H$ gator som går i öst-västlig riktning och $W$ gator som går i syd-nordlig riktning, samt att det finns $Q$ kandidatkorsningar för kidnappningsplatsen.
• Den andra raden i indatan innehåller $H$ mellanslagsseparerade heltal $A_1,A_2,\ldots,A_H$. Detta betyder att trängselgraden för den $i$-te gatan ($1 \le i \le H$) från norr som går i öst-västlig riktning är $A_i$.
• Den tredje raden i indatan innehåller $W$ mellanslagsseparerade heltal $B_1,B_2,\ldots,B_W$. Detta betyder att trängselgraden för den $j$-te gatan ($1 \le j \le W$) från väster som går i syd-nordlig riktning är $B_j$.
• Den $k$-te raden ($1 \le k \le Q$) av de följande $Q$ raderna innehåller två mellanslagsseparerade heltal $S_k,T_k$. Detta betyder att den $k$-te kandidatkorsningen för kidnappningsplatsen är korsningen mellan den $S_k$-te gatan från norr som går i öst-västlig riktning och den $T_k$-te gatan från väster som går i syd-nordlig riktning.

Utdata

Skriv $Q$ rader till standard utmatning. Den $k$-te raden i utdatan ska innehålla ett heltal, den maximalt möjliga körsträckan (i kilometer) från den $k$-te kandidatkorsningen för kidnappningsplatsen.

Begränsningar

All indata uppfyller följande villkor.

• $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$ heltalen $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ är alla olika.
• $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$).

Deluppgifter

Det finns 5 deluppgifter. Poängen och de ytterligare begränsningarna för varje deluppgift är som följer:

Deluppgift 1 [13 poäng]

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

Deluppgift 2 [10 poäng]

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

Deluppgift 3 [17 poäng]

• $Q=1$.

Deluppgift 4 [4 poäng]

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

Deluppgift 5 [56 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 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

Förklaring

För den tredje frågan uppnår körsträckan till exempel det maximala värdet om brottslingarna rörde sig på följande sätt:

• De åkte österut i 1 kilometer från korsningen mellan den andra gatan från norr och den andra gatan från väster.
• De kunde åka söderut eller norrut från korsningen mellan den andra gatan från norr och den tredje gatan från väster. De valde att åka söderut i 1 kilometer.
• De kunde endast åka västerut från korsningen mellan den tredje gatan från norr och den tredje gatan från väster. De åkte västerut i 1 kilometer.
• De kunde endast åka västerut från korsningen mellan den tredje gatan från norr och den andra gatan från väster. De åkte västerut i 1 kilometer.
• De kunde inte åka vidare från korsningen mellan den tredje gatan från norr och den första gatan från väster. De slutade röra sig på den platsen.

Om de rörde sig som ovan är körsträckan 4 kilometer.

Indata 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