Karena soal-soal yang menantang, beberapa peserta memutuskan untuk melarikan diri dari kontes ini. Namun, untuk mencegah hal itu, para pembuat soal yang JAHAT membuat labirin di pintu keluar stadion. Labirin tersebut berupa petak-petak berukuran $n \times m$, yang memiliki pintu masuk, pintu keluar, dan $k$ lubang hitam. Peserta yang tidak sengaja menginjak lubang hitam mana pun akan jatuh ke dalamnya sehingga tidak akan pernah dapat melarikan diri dari kontes.

Lebih buruk lagi, para pembuat soal juga dapat mengubah koordinat pintu masuk dan pintu keluar. Anda, peserta malang yang mulai dari pintu masuk dan ingin mencapai pintu keluar tanpa menginjak lubang hitam mana pun, hanya dapat bergerak ke salah satu dari empat petak yang bertetangga pada setiap langkah. Anda ingin mengetahui, setelah setiap kali para pembuat soal mengubah koordinat pintu masuk dan pintu keluar, berapa jumlah minimum langkah yang diperlukan untuk mencapai pintu keluar dari pintu masuk?

Masukan

Baris pertama masukan berisi empat bilangan bulat $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$), yang berturut-turut menyatakan banyaknya baris, banyaknya kolom, banyaknya lubang hitam dalam labirin, dan banyaknya kueri.

Sebanyak $k$ baris berikutnya berisi deskripsi lubang-lubang hitam. Setiap baris berisi dua bilangan bulat $x,y$ ($1 \le x \le n$, $1 \le y \le m$), yang menyatakan koordinat sebuah lubang hitam. Tidak ada dua lubang hitam yang terletak di posisi yang sama.

Sebanyak $q$ baris terakhir berisi deskripsi kueri. Setiap dari $q$ baris berisi empat bilangan bulat $x_s,y_s,x_t,y_t$ ($1 \le x_s,x_t \le n$, $1 \le y_s,y_t \le m$), dengan $(x_s,y_s)$ merupakan koordinat pintu masuk dan $(x_t,y_t)$ merupakan koordinat pintu keluar.

Keluaran

Untuk setiap kueri, keluarkan sebuah bilangan pada satu baris yang menyatakan jumlah minimum langkah yang diperlukan untuk mencapai pintu keluar dari pintu masuk. Jika pintu keluar tidak mungkin dicapai, keluarkan $-1$. Hal ini harus dianggap mustahil jika pintu masuk atau pintu keluar berimpit dengan sebuah lubang hitam.

Contoh

Masukan 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

Keluaran 1

6
0
-1
4
-1
5
-1

Masukan 2

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

Keluaran 2

-1

Catatan

Gambar labirin dan kueri pertama pada contoh data pertama ditunjukkan di bawah.

(a) Labirin. (b) Salah satu lintasan terpendek yang mungkin untuk kueri pertama.

Keterangan: pintu masuk, pintu keluar, lubang hitam, satu langkah.

Gambar 1: Ilustrasi untuk contoh data uji.