Z powodu trudnych zadań część uczestników postanawia uciec z tych zawodów. Aby temu zapobiec, ŹLI autorzy zadań zbudowali jednak labirynt przy wyjściu ze stadionu. Labirynt składa się z siatki $n \times m$, na której znajdują się wejście, wyjście i $k$ czarnych dziur. Uczestnicy, którzy przypadkowo wejdą do którejkolwiek czarnej dziury, wpadną do niej i już nigdy nie zdołają uciec z zawodów.

Co gorsza, autorzy zadań mogą również zmieniać współrzędne wejścia i wyjścia. Ty, biedny uczestnik, zaczynasz przy wejściu i chcesz dotrzeć do wyjścia, nie wchodząc do żadnej czarnej dziury. W każdym kroku możesz przejść tylko do jednej z czterech sąsiednich komórek. Chcesz wiedzieć, po każdej zmianie współrzędnych wejścia i wyjścia przez autorów, jaka jest minimalna liczba kroków potrzebnych do dotarcia z wejścia do wyjścia.

Wejście

Pierwszy wiersz wejścia zawiera cztery liczby całkowite $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$), oznaczające odpowiednio liczbę wierszy, liczbę kolumn, liczbę czarnych dziur w labiryncie oraz liczbę zapytań.

Kolejnych $k$ wierszy zawiera opis czarnych dziur. Każdy z tych wierszy zawiera dwie liczby całkowite $x,y$ ($1 \le x \le n$, $1 \le y \le m$), oznaczające współrzędne czarnej dziury. Żadne dwie czarne dziury nie znajdują się w tym samym miejscu.

Ostatnich $q$ wierszy zawiera opis zapytań. Każdy z nich zawiera cztery liczby całkowite $x_s,y_s,x_t,y_t$ ($1 \le x_s,x_t \le n$, $1 \le y_s,y_t \le m$), gdzie $(x_s,y_s)$ to współrzędne wejścia, a $(x_t,y_t)$ — wyjścia.

Wyjście

Dla każdego zapytania wypisz w osobnym wierszu liczbę oznaczającą minimalną liczbę kroków potrzebnych do dotarcia z wejścia do wyjścia. Jeśli dotarcie do wyjścia jest niemożliwe, wypisz zamiast tego $-1$. Przypadek, w którym wejście lub wyjście pokrywa się z czarną dziurą, należy uznać za niemożliwy.

Przykład

Wejście 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

Wyjście 1

6
0
-1
4
-1
5
-1

Wejście 2

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

Wyjście 2

-1

Uwagi

Poniżej przedstawiono rysunki labiryntu oraz pierwszego zapytania z pierwszego przykładu.

(a) Labirynt. (b) Jedna z możliwych najkrótszych ścieżek dla pierwszego zapytania. Legenda: wejście, wyjście, czarna dziura, jeden krok. Rysunek 1: Rysunki dla danych przykładowych.