Par une journée ensoleillée, un enlèvement a eu lieu à un carrefour d'une ville. Les suspects sont Anna et Bruno, qui se seraient enfuis en voiture depuis le lieu de l'enlèvement. La voiture n'a pas encore été retrouvée. La police la recherche toujours.

La zone urbaine où les criminels ont circulé est une ville en forme de grille rectangulaire, avec $H$ rues orientées est-ouest et $W$ rues orientées sud-nord. La distance entre deux carrefours voisins est de 1 kilomètre.

Chaque rue possède un entier appelé degré de congestion. Le degré de congestion de la $i$-ème rue orientée est-ouest en partant du nord ($1 \le i \le H$) est $A_i$, et celui de la $j$-ème rue orientée sud-nord en partant de l'ouest ($1 \le j \le W$) est $B_j$. Ces $H+W$ valeurs sont toutes distinctes. Le degré de congestion d'une rue est le même en tout point de celle-ci.

L'enquête de la police a révélé que les criminels se sont déplacés dans la ville de la manière suivante :

• Ils ne sont pas sortis de la ville et n'ont pas quitté les rues.
• Au départ, ils ont choisi l'une des directions possibles depuis le lieu de l'enlèvement et ont avancé dans cette direction.
• Lorsqu'ils arrivaient à un carrefour, si le degré de congestion de la rue transversale était supérieur à celui de leur rue actuelle, ils tournaient à ce carrefour. S'il était possible de tourner dans les deux directions, ils pouvaient choisir l'une ou l'autre.
• Lorsqu'ils arrivaient à un carrefour, si le degré de congestion de leur rue actuelle était supérieur à celui de la rue transversale, ils continuaient tout droit. Toutefois, s'ils se trouvaient à la limite de la ville et ne pouvaient pas continuer tout droit, ils s'arrêtaient sur place.

Il existe $Q$ carrefours candidats pour le lieu de l'enlèvement, tous distincts. Pour déterminer le nombre d'enquêteurs, la police souhaite connaître, pour chacun de ces carrefours, la distance maximale que les criminels ont pu parcourir en supposant que l'enlèvement a eu lieu à cet endroit.

Pour chacune des $Q$ requêtes, calculez la distance maximale pouvant être parcourue depuis le carrefour candidat donné.

Tâche

Étant donnés les degrés de congestion des rues de la ville et les $Q$ carrefours candidats pour le lieu de l'enlèvement, écrivez un programme qui calcule la distance maximale pouvant être parcourue depuis chaque carrefour candidat.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient trois entiers $H,W,Q$ séparés par des espaces. Cela signifie que la ville est une grille rectangulaire comportant $H$ rues orientées est-ouest et $W$ rues orientées sud-nord, et qu'il existe $Q$ carrefours candidats pour le lieu de l'enlèvement.
• La deuxième ligne contient $H$ entiers $A_1,A_2,\ldots,A_H$ séparés par des espaces. Cela signifie que le degré de congestion de la $i$-ème rue orientée est-ouest en partant du nord ($1 \le i \le H$) est $A_i$.
• La troisième ligne contient $W$ entiers $B_1,B_2,\ldots,B_W$ séparés par des espaces. Cela signifie que le degré de congestion de la $j$-ème rue orientée sud-nord en partant de l'ouest ($1 \le j \le W$) est $B_j$.
• La $k$-ème ligne ($1 \le k \le Q$) parmi les $Q$ lignes suivantes contient deux entiers $S_k,T_k$ séparés par un espace. Cela signifie que le $k$-ème carrefour candidat est l'intersection de la $S_k$-ème rue orientée est-ouest en partant du nord et de la $T_k$-ème rue orientée sud-nord en partant de l'ouest.

Sortie

Écrivez $Q$ lignes sur la sortie standard. La $k$-ème ligne doit contenir un entier : la distance maximale pouvant être parcourue (en kilomètres) depuis le $k$-ème carrefour candidat pour le lieu de l'enlèvement.

Contraintes

Toutes les données d'entrée vérifient les conditions suivantes.

• $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$).
• Les $H+W$ entiers $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ sont tous distincts.
• $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$).

Sous-tâches

Il y a 5 sous-tâches. Leurs scores et leurs contraintes supplémentaires sont les suivants :

Sous-tâche 1 [13 points]

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

Sous-tâche 2 [10 points]

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

Sous-tâche 3 [17 points]

• $Q=1$.

Sous-tâche 4 [4 points]

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

Sous-tâche 5 [56 points]

Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

4
5
4
4
2

Remarque

Par exemple, pour la troisième requête, la distance parcourue atteint sa valeur maximale si les criminels se déplacent ainsi :

• Ils parcourent 1 kilomètre vers l'est depuis l'intersection de la deuxième rue en partant du nord et de la deuxième rue en partant de l'ouest.
• Depuis l'intersection de la deuxième rue en partant du nord et de la troisième rue en partant de l'ouest, ils peuvent aller vers le sud ou vers le nord. Ils choisissent de parcourir 1 kilomètre vers le sud.
• Depuis l'intersection de la troisième rue en partant du nord et de la troisième rue en partant de l'ouest, ils peuvent uniquement aller vers l'ouest. Ils parcourent 1 kilomètre vers l'ouest.
• Depuis l'intersection de la troisième rue en partant du nord et de la deuxième rue en partant de l'ouest, ils peuvent uniquement aller vers l'ouest. Ils parcourent 1 kilomètre vers l'ouest.
• Ils ne peuvent plus avancer depuis l'intersection de la troisième rue en partant du nord et de la première rue en partant de l'ouest. Ils s'y arrêtent.

En se déplaçant ainsi, ils parcourent 4 kilomètres.

Entrée 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

Sortie 2

7
6
9
4
6
9