Wegen der schwierigen Aufgaben beschließen einige Teilnehmer, aus diesem Wettbewerb zu fliehen. Um das zu verhindern, haben die BÖSEN Aufgabensteller jedoch am Ausgang des Stadions ein Labyrinth gebaut. Das Labyrinth besteht aus einem Gitter der Größe $n\times m$, in dem sich der Eingang, der Ausgang und $k$ schwarze Löcher befinden. Teilnehmer, die versehentlich ein schwarzes Loch betreten, fallen hinein und können dem Wettbewerb nie mehr entkommen.

Noch schlimmer: Die Aufgabensteller können auch die Koordinaten von Eingang und Ausgang verändern. Sie sind ein armer Teilnehmer, starten am Eingang und möchten den Ausgang erreichen, ohne eines der schwarzen Löcher zu betreten. In jedem Schritt können Sie sich nur in eine der vier benachbarten Zellen bewegen. Sie möchten nach jeder Änderung der Koordinaten von Eingang und Ausgang wissen, wie viele Schritte mindestens benötigt werden, um vom Eingang zum Ausgang zu gelangen.

Eingabe

Die erste Eingabezeile enthält vier ganze Zahlen $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$). Sie bezeichnen der Reihe nach die Anzahl der Zeilen, der Spalten, der schwarzen Löcher im Labyrinth und der Anfragen.

Die folgenden $k$ Zeilen beschreiben die schwarzen Löcher. Jede enthält zwei ganze Zahlen $x,y$ ($1\le x\le n$, $1\le y\le m$), die Koordinaten eines schwarzen Lochs. Keine zwei schwarzen Löcher befinden sich an derselben Position.

Die letzten $q$ Zeilen beschreiben die Anfragen. Jede enthält vier ganze Zahlen $x_s,y_s,x_t,y_t$ ($1\le x_s,x_t\le n$, $1\le y_s,y_t\le m$), wobei $(x_s,y_s)$ die Koordinaten des Eingangs und $(x_t,y_t)$ die des Ausgangs sind.

Ausgabe

Geben Sie für jede Anfrage in einer Zeile eine Zahl aus: die kleinste Anzahl benötigter Schritte vom Eingang zum Ausgang. Falls der Ausgang nicht erreichbar ist, geben Sie stattdessen $-1$ aus. Befindet sich der Eingang oder der Ausgang auf einem schwarzen Loch, gilt der Ausgang als unerreichbar.

Beispiele

Eingabe 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

Ausgabe 1

6
0
-1
4
-1
5
-1

Eingabe 2

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

Ausgabe 2

-1

Hinweis

Die folgenden Abbildungen zeigen das Labyrinth und die erste Anfrage des ersten Beispiels.

(a) Das Labyrinth. (b) Ein möglicher kürzester Weg für die erste Anfrage. Legende: Eingang, Ausgang, schwarzes Loch, ein Schritt.

Abbildung 1: Abbildungen zu den Beispieltestdaten