Xiao T a planifié la zone d'exposition sous la forme d'une grille bidimensionnelle de taille $n \times n$. La périphérie de la grille est entourée par une rangée de murs d'exposition, c'est-à-dire que toutes les cases dont l'abscisse ou l'ordonnée est égale à $0$ ou $n+1$ sont des cases de mur d'exposition. De plus, $m$ cases de mur d'exposition sont dispersées à l'intérieur de la zone d'exposition, la $i$-ième ($1 \le i \le m$) ayant pour coordonnées $(x_i, y_i)$. Il est garanti que toutes les cases de mur d'exposition forment une structure 4-connexe.

Après des tests de mise en scène sur le terrain, Xiao T a résumé les règles de consommation de temps pour se déplacer entre les cases de la grille. Plus précisément, il existe deux manières de se déplacer entre les cases :

• Se déplacer d'une case dans les directions haut, bas, gauche ou droite, c'est-à-dire passer de $(x, y)$ à l'une des cases adjacentes $(x-1, y)$, $(x+1, y)$, $(x, y-1)$, $(x, y+1)$, ce qui consomme $2$ unités de temps.
• Se déplacer d'une case en diagonale, c'est-à-dire passer de $(x, y)$ à l'une des cases diagonales $(x-1, y-1)$, $(x-1, y+1)$, $(x+1, y-1)$, $(x+1, y+1)$, ce qui consomme $3$ unités de temps.

Bien entendu, la position cible du déplacement ne peut pas être une case de mur d'exposition. Remarque : lors d'un déplacement en diagonale, il est possible de passer directement par l'interstice entre deux cases de mur d'exposition diagonales. Par exemple, même si $(x, y+1)$ et $(x+1, y)$ sont toutes deux des cases de mur d'exposition, il est toujours possible de consommer $3$ unités de temps pour se déplacer directement de $(x, y)$ à $(x+1, y+1)$ en diagonale.

Xiao S a disposé un total de $q$ trésors dans la zone d'exposition. Pour le $i$-ième trésor ($1 \le i \le q$), elle annonce sa position $(tx_i, ty_i)$, tandis que votre position au moment de l'annonce est $(sx_i, sy_i)$. Afin d'obtenir chaque trésor le plus rapidement possible, vous devez calculer le temps minimal nécessaire pour vous déplacer de votre position actuelle à la position du trésor.

Entrée

La première ligne de l'entrée contient trois entiers positifs $n, m, q$ ($1 \le n \le 10^5$, $1 \le m, q \le 3 \times 10^5$).

Les $m$ lignes suivantes contiennent chacune deux entiers positifs $x_i, y_i$ ($1 \le x_i, y_i \le n$), représentant les coordonnées du $i$-ième mur d'exposition. Il est garanti que toutes les coordonnées $(x_i, y_i)$ sont distinctes.

Les $q$ lignes suivantes contiennent chacune quatre entiers positifs $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$), représentant votre position et la position du trésor lors de l'annonce du $i$-ième trésor. Il est garanti que $(sx_i, sy_i)$ et $(tx_i, ty_i)$ ne sont pas des cases de mur d'exposition.

Sortie

Affichez $q$ lignes, chacune contenant un entier représentant la réponse. En particulier, si vous ne pouvez pas atteindre la position du trésor, affichez $-1$.

Exemples

Entrée 1

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

Sortie 1

2
16
11
10
11

Remarque

Pour le deuxième trésor, vous pouvez vous déplacer le long du chemin suivant : $(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$, le temps total consommé est $2 + 3 + 3 + 3 + 2 + 3 = 16$.