Do các bài toán quá khó, một số thí sinh quyết định trốn khỏi cuộc thi này. Tuy nhiên, để ngăn điều đó xảy ra, các tác giả ĐỘC ÁC đã tạo một mê cung tại lối ra của sân vận động. Mê cung là một lưới $n \times m$, trên đó có lối vào, lối ra và $k$ hố đen. Thí sinh vô tình bước vào bất kỳ hố đen nào sẽ rơi xuống đó và không bao giờ có thể thoát khỏi cuộc thi.

Tệ hơn nữa, các tác giả còn có thể thay đổi tọa độ lối vào và lối ra. Bạn, một thí sinh đáng thương, xuất phát từ lối vào và muốn tới lối ra mà không bước vào hố đen nào, mỗi bước chỉ có thể đi tới một trong bốn ô kề cạnh. Bạn muốn biết sau mỗi lần các tác giả thay đổi tọa độ lối vào và lối ra, số bước ít nhất cần thiết để đi từ lối vào tới lối ra là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa bốn số nguyên $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$), lần lượt biểu thị số hàng, số cột, số hố đen trong mê cung và số truy vấn.

$k$ dòng tiếp theo mô tả các hố đen. Mỗi dòng chứa hai số nguyên $x,y$ ($1 \le x \le n$, $1 \le y \le m$), biểu thị tọa độ một hố đen. Không có hai hố đen nào nằm ở cùng vị trí.

$q$ dòng cuối cùng mô tả các truy vấn. Mỗi dòng trong $q$ dòng chứa bốn số nguyên $x_s,y_s,x_t,y_t$ ($1 \le x_s,x_t \le n$, $1 \le y_s,y_t \le m$), trong đó $(x_s,y_s)$ là tọa độ lối vào và $(x_t,y_t)$ là lối ra.

Dữ liệu ra

Với mỗi truy vấn, in một số trên một dòng, biểu thị số bước ít nhất cần để đi từ lối vào tới lối ra. Nếu không thể tới lối ra, in -1. Nếu lối vào hoặc lối ra trùng với một hố đen thì cũng được coi là không thể.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

6
0
-1
4
-1
5
-1

Dữ liệu vào 2

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

Dữ liệu ra 2

-1

Ghi chú

Các hình minh họa mê cung và truy vấn thứ nhất của dữ liệu ví dụ thứ nhất được cho bên dưới.

(a) Mê cung. (b) Một đường đi ngắn nhất có thể cho truy vấn thứ nhất.

Chú giải: lối vào, lối ra, hố đen, một bước.

Hình 1: Các hình minh họa dữ liệu kiểm thử ví dụ.