Á sólríkum degi átti sér stað mannrán á gatnamótum í borg einni. Grunað er að glæpamennirnir hafi verið Anna og Bruno, og að þau hafi flúið af vettvangi mannránssins á bíl. Bíllinn er enn ófundinn. Lögreglan leitar hans enn þann dag í dag.

Þéttbýlissvæðið þar sem glæpamennirnir óku bílnum er borg í formi rétthyrnds nets með $H$ götum sem liggja í austur-vestur-átt og $W$ götum sem liggja í suður-norður-átt. Fjarlægðin milli tvennra aðliggjandi gatnamóta er 1 kílómetri.

Hver gata hefur heiltölu, umferðarþungastig. Umferðarþungastig $i$-tu götunnar ($1 \le i \le H$) talið úr norðri sem liggur í austur-vestur-átt er $A_i$, og umferðarþungastig $j$-tu götunnar ($1 \le j \le W$) talið úr vestri sem liggur í suður-norður-átt er $B_j$. Þessi $H+W$ gildi eru öll ólík innbyrðis. Fyrir hverja götu hefur umferðarþungastigið sama gildi á öllum punktum hennar.

Rannsókn lögreglunnar leiddi í ljós að glæpamennirnir ferðuðust um borgina á eftirfarandi hátt:

• Þau fóru ekki út fyrir borgina og þau fóru ekki út af götunum.
• Í upphafi völdu glæpamennirnir eina af mögulegum akstursstefnum frá vettvangi mannránssins og héldu í þá átt.
• Þegar þau komu að gatnamótum, ef umferðarþungastig þvergötunnar var hærra en á núverandi götu, beygðu þau á þeim gatnamótum. Ef hægt var að beygja í báðar áttir gátu þau valið hvora sem var.
• Þegar þau komu að gatnamótum, ef umferðarþungastig núverandi götu var hærra en á þvergötunni, héldu þau áfram beint. Hins vegar, ef þau voru við mörk borgarinnar og gátu ekki haldið áfram beint, stöðvuðu þau á þeim stað.

Það eru $Q$ gatnamót sem koma til greina sem vettvangur mannránssins. Þessi $Q$ gatnamót eru öll ólík innbyrðis. Til að ákvarða fjölda rannsóknarlögreglumanna vill lögreglan vita, fyrir hver gatnamót sem koma til greina, hámarks mögulega vegalengd sem glæpamennirnir gátu ekið miðað við að mannránið hafi átt sér stað þar.

Fyrir hverja af $Q$ fyrirspurnum skal reikna hámarks mögulega vegalengd frá hinum gefnu gatnamótum.

Verkefni

Gefið umferðarþungastig gatnanna í borginni og $Q$ gatnamót sem koma til greina sem vettvangur mannránssins, skrifið forrit sem reiknar hámarks mögulega vegalengd frá hverjum gatnamótum sem koma til greina.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki.

• Fyrsta línan í inntakinu inniheldur þrjár heiltölur $H,W,Q$ aðskildar með bili. Þetta þýðir að borgin sé rétthyrnt net með $H$ götum sem liggja í austur-vestur-átt og $W$ götum sem liggja í suður-norður-átt, og að $Q$ gatnamót komi til greina sem vettvangur mannránssins.
• Önnur línan í inntakinu inniheldur $H$ heiltölur $A_1,A_2,\ldots,A_H$ aðskildar með bili. Þetta þýðir að umferðarþungastig $i$-tu götunnar ($1 \le i \le H$) úr norðri sem liggur í austur-vestur-átt sé $A_i$.
• Þriðja línan í inntakinu inniheldur $W$ heiltölur $B_1,B_2,\ldots,B_W$ aðskildar með bili. Þetta þýðir að umferðarþungastig $j$-tu götunnar ($1 \le j \le W$) úr vestri sem liggur í suður-norður-átt sé $B_j$.
• $k$-ta línan ($1 \le k \le Q$) af næstu $Q$ línum inniheldur tvær heiltölur $S_k,T_k$ aðskildar með bili. Þetta þýðir að $k$-tu gatnamótin sem koma til greina sem vettvangur mannránssins séu gatnamót $S_k$-tu götunnar úr norðri sem liggur í austur-vestur-átt og $T_k$-tu götunnar úr vestri sem liggur í suður-norður-átt.

Úttak

Skrifið $Q$ línur í staðalúttak. $k$-ta línan í úttakinu á að innihalda heiltölu, hámarks mögulega vegalengd (í kílómetrum) frá $k$-tu gatnamótunum sem koma til greina sem vettvangur mannránssins.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

• $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$).
• Heiltölurnar $H+W$, $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$, eru allar ólíkar innbyrðis.
• $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$).

Undirverkefni

Það eru 5 undirverkefni. Stigagjöf og viðbótarskilyrði hvers undirverkefnis eru sem hér segir:

Undirverkefni 1 [13 stig]

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

Undirverkefni 2 [10 stig]

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

Undirverkefni 3 [17 stig]

• $Q=1$.

Undirverkefni 4 [4 stig]

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

Undirverkefni 5 [56 stig]

Það eru engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

4
5
4
4
2

Athugasemd

Til dæmis, fyrir þriðju fyrirspurnina nær vegalengdin hámarksgildi ef glæpamennirnir ferðuðust á eftirfarandi hátt:

• Þau fóru í austur um 1 kílómetra frá gatnamótum annarrar götu úr norðri og annarrar götu úr vestri.
• Þau gátu farið í suður eða norður frá gatnamótum annarrar götu úr norðri og þriðju götu úr vestri. Þau völdu að fara í suður um 1 kílómetra.
• Þau gátu aðeins farið í vestur frá gatnamótum þriðju götu úr norðri og þriðju götu úr vestri. Þau fóru í vestur um 1 kílómetra.
• Þau gátu aðeins farið í vestur frá gatnamótum þriðju götu úr norðri og annarrar götu úr vestri. Þau fóru í vestur um 1 kílómetra.
• Þau gátu ekki farið lengra frá gatnamótum þriðju götu úr norðri og fyrstu götu úr vestri. Þau stöðvuðu á þeim stað.

Ef þau ferðuðust eins og lýst er hér að ofan er vegalengdin 4 kílómetrar.

Inntak 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

Úttak 2

7
6
9
4
6
9