En raison de la difficulté des problèmes, certains participants décident de fuir ce concours. Pour les en empêcher, les MALÉFIQUES auteurs des problèmes ont construit un labyrinthe à la sortie du stade. Le labyrinthe est une grille de $n \times m$ cases, sur laquelle se trouvent une entrée, une sortie et $k$ trous noirs. Les participants qui marchent accidentellement sur un trou noir y tombent et ne peuvent donc plus jamais échapper au concours.

Pire encore, les auteurs peuvent modifier les coordonnées de l'entrée et de la sortie. Vous, pauvre participant, partez de l'entrée et souhaitez atteindre la sortie sans marcher sur aucun trou noir. À chaque pas, vous ne pouvez vous déplacer que vers l'une des quatre cases adjacentes. Après chaque modification des coordonnées de l'entrée et de la sortie, vous voulez connaître le nombre minimal de pas nécessaire pour rejoindre la sortie depuis l'entrée.

Entrée

La première ligne de l'entrée contient quatre entiers $n,m,k,q$ ($1 \le n,m \le 200\,000$, $nm \le 200\,000$, $0 \le k \le 42$, $1 \le q \le 100\,000$), qui désignent respectivement le nombre de lignes, le nombre de colonnes, le nombre de trous noirs du labyrinthe et le nombre de requêtes.

Les $k$ lignes suivantes décrivent les trous noirs. Chacune contient deux entiers $x,y$ ($1 \le x \le n$, $1 \le y \le m$), les coordonnées d'un trou noir. Deux trous noirs n'occupent jamais la même position.

Les $q$ dernières lignes décrivent les requêtes. Chacune contient quatre entiers $x_s,y_s,x_t,y_t$ ($1 \le x_s,x_t \le n$, $1 \le y_s,y_t \le m$), où $(x_s,y_s)$ est la position de l'entrée et $(x_t,y_t)$ celle de la sortie.

Sortie

Pour chaque requête, affichez sur une ligne un nombre indiquant le nombre minimal de pas nécessaire pour atteindre la sortie depuis l'entrée. Si la sortie est inaccessible, affichez $-1$. Le trajet doit être considéré comme impossible lorsque l'entrée ou la sortie coïncide avec un trou noir.

Exemples

Entrée 1

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

Sortie 1

6
0
-1
4
-1
5
-1

Entrée 2

2 3 2 1
1 2
2 1
1 1 2 3

Sortie 2

-1

Remarque

Le labyrinthe et la première requête du premier exemple sont représentés ci-dessous.

(a) Le labyrinthe. (b) Un plus court chemin possible pour la première requête.

Légende : entrée ; sortie ; trou noir ; un pas.

Figure 1 : représentations des données d'exemple.