Aurinkoisena päivänä eräässä kaupungin risteyksessä tapahtui sieppaus. Rikollisiksi epäillään Annaa ja Brunoa, jotka pakenivat sieppauspaikalta autolla. Autoa ei ole vielä löydetty. Poliisi etsii sitä edelleen.

Kaupunkialue, jolla rikolliset ajoivat autolla, on suorakulmaisen ruudukon muotoinen kaupunki, jossa on $H$ itä–länsi-suuntaista katua ja $W$ etelä–pohjoinen-suuntaista katua. Kahden vierekkäisen risteyksen välinen etäisyys on 1 kilometri.

Jokaisella kadulla on kokonaislukuarvo, ruuhkaisuusaste. Pohjoisesta lukien $i$-nnen ($1 \le i \le H$) itä–länsi-suuntaisen kadun ruuhkaisuusaste on $A_i$, ja lännestä lukien $j$-nnen ($1 \le j \le W$) etelä–pohjoinen-suuntaisen kadun ruuhkaisuusaste on $B_j$. Nämä $H+W$ arvoa ovat kaikki keskenään erisuuria. Kullakin kadulla ruuhkaisuusasteella on sama arvo kadun jokaisessa pisteessä.

Poliisin tutkinnassa selvisi, että rikolliset liikkuivat kaupungissa seuraavalla tavalla:

• He eivät poistuneet kaupungista eivätkä poikenneet kaduilta.
• Aluksi rikolliset valitsivat yhden sieppauspaikalta mahdollisista kulkusuunnista ja lähtivät liikkeelle siihen suuntaan.
• Kun he saapuivat risteykseen, jossa risteävän kadun ruuhkaisuusaste oli suurempi kuin nykyisen kadun, he kääntyivät kyseisessä risteyksessä. Jos kääntyminen oli mahdollista molempiin suuntiin, he saattoivat valita niistä kumman tahansa.
• Kun he saapuivat risteykseen, jossa nykyisen kadun ruuhkaisuusaste oli suurempi kuin risteävän kadun, he jatkoivat suoraan. Jos he kuitenkin olivat kaupungin reunalla eivätkä voineet jatkaa suoraan, he pysähtyivät kyseiseen paikkaan.

Sieppauspaikaksi on $Q$ risteysehdotusta. Nämä $Q$ ehdokasta ovat keskenään erisuuria. Tutkijoiden määrän päättämiseksi poliisi haluaa tietää jokaiselle risteysehdotukselle rikollisten suurimman mahdollisen kulkumatkan olettaen, että sieppaus tapahtui kyseisessä paikassa.

Laske jokaiselle $Q$ kyselylle suurin mahdollinen kulkumatka annetusta risteysehdotuksesta.

Tehtävä

Kun annetaan kaupungin katujen ruuhkaisuusasteet ja $Q$ risteysehdotusta sieppauspaikaksi, kirjoita ohjelma, joka laskee suurimman mahdollisen kulkumatkan kustakin risteysehdotuksesta.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• Syötteen ensimmäinen rivi sisältää kolme välilyönnillä erotettua kokonaislukua $H,W,Q$. Tämä tarkoittaa, että kaupunki on suorakulmainen ruudukko, jossa on $H$ itä–länsi-suuntaista katua ja $W$ etelä–pohjoinen-suuntaista katua, ja sieppauspaikaksi on $Q$ risteysehdotusta.
• Syötteen toinen rivi sisältää $H$ välilyönnillä erotettua kokonaislukua $A_1,A_2,\ldots,A_H$. Tämä tarkoittaa, että pohjoisesta lukien $i$-nnen ($1 \le i \le H$) itä–länsi-suuntaisen kadun ruuhkaisuusaste on $A_i$.
• Syötteen kolmas rivi sisältää $W$ välilyönnillä erotettua kokonaislukua $B_1,B_2,\ldots,B_W$. Tämä tarkoittaa, että lännestä lukien $j$-nnen ($1 \le j \le W$) etelä–pohjoinen-suuntaisen kadun ruuhkaisuusaste on $B_j$.
• Seuraavista $Q$ rivistä $k$-s rivi ($1 \le k \le Q$) sisältää kaksi välilyönnillä erotettua kokonaislukua $S_k,T_k$. Tämä tarkoittaa, että $k$-s risteysehdotus sieppauspaikaksi on pohjoisesta lukien $S_k$-nnen itä–länsi-suuntaisen kadun ja lännestä lukien $T_k$-nnen etelä–pohjoinen-suuntaisen kadun risteys.

Tuloste

Kirjoita vakiotulosteeseen $Q$ riviä. Tulosteen $k$-nnen rivin tulee sisältää kokonaisluku, suurin mahdollinen kulkumatka (kilometreinä) $k$-nnesta sieppauspaikan risteysehdotuksesta.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

• $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$).
• Nämä $H+W$ kokonaislukua $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ ovat keskenään erisuuria.
• $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$).

Osatehtävät

Tehtävässä on 5 osatehtävää. Kunkin osatehtävän pistemäärä ja lisärajoitukset ovat seuraavat:

Osatehtävä 1 [13 pistettä]

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

Osatehtävä 2 [10 pistettä]

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

Osatehtävä 3 [17 pistettä]

• $Q=1$.

Osatehtävä 4 [4 pistettä]

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

Osatehtävä 5 [56 pistettä]

Ei ole lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

4
5
4
4
2

Huomautus

Esimerkiksi kolmannessa kyselyssä kulkumatka saavuttaa suurimman arvonsa, jos rikolliset liikkuivat seuraavalla tavalla:

• He kulkivat itään 1 kilometrin pohjoisesta lukien toisen kadun ja lännestä lukien toisen kadun risteyksestä.
• He saattoivat kulkea etelään tai pohjoiseen pohjoisesta lukien toisen kadun ja lännestä lukien kolmannen kadun risteyksestä. He valitsivat kulkea etelään 1 kilometrin.
• He saattoivat kulkea vain länteen pohjoisesta lukien kolmannen kadun ja lännestä lukien kolmannen kadun risteyksestä. He kulkivat länteen 1 kilometrin.
• He saattoivat kulkea vain länteen pohjoisesta lukien kolmannen kadun ja lännestä lukien toisen kadun risteyksestä. He kulkivat länteen 1 kilometrin.
• He eivät voineet liikkua eteenpäin pohjoisesta lukien kolmannen kadun ja lännestä lukien ensimmäisen kadun risteyksestä. He pysähtyivät kyseiseen paikkaan.

Jos he liikkuivat yllä kuvatulla tavalla, kulkumatka on 4 kilometriä.

Syöte 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

Tuloste 2

7
6
9
4
6
9