시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 1024 MB2814940.909%

문제

Due to the challenging problems, some of the contestants decide to escape from this contest. However, to prevent this from happening, the EVIL problem setters made a labyrinth at the stadium's exit. The labyrinth is made of an $n \times m$ grid, on which lie the entrance and the exit, and $k$ black holes. Contestants who accidentally step into any black hole will fall into it and thus can never escape from the contest.

What's worse, the problem setters may also adjust the coordinates of the entrance and the exit. You, a poor contestant, who start from the entrance and wish to reach the exit without stepping into any of the black holes, can only move to one of the four adjacent cells in each step. You want to know, after each time the problem setters change the coordinates of the entrance and the exit, what's the minimum number of steps needed to reach the exit starting from the entrance?

입력

The first line of the input contains four integers $n, m, k, q$ $(1 \leq n, m \leq 200\,000, nm \leq 200\,000, 0 \leq k \leq 42,$ $ 1 \leq q \leq 100\,000)$, denoting the number of rows, the number of columns, the number of black holes in the labyrinth, and the number of queries, respectively.

The following $k$ lines contain the description of the black holes. Each of these lines contains two integers $x, y$ $(1\leq x \leq n,1\leq y \leq m)$, denoting the coordinates of a black hole. No two black holes are located at the same position.

The last $q$ lines contain the description of the queries. Each of the $q$ lines contains four integers $x_s, y_s, x_t, y_t$ $(1 \leq x_s, x_t\leq n, 1\leq y_s, y_t \leq m)$, where $(x_s, y_s)$ is the coordinates of the entrace and $(x_t, y_t)$ is the exit.

출력

For each query, output a number in a line, denoting the minimum number of steps needed to reach the exit starting from the entrance. If it is impossible to reach the exit, output -1 instead. It should be considered impossible when the entrace or the exit coincides with a black hole.

예제 입력 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

예제 출력 1

6
0
-1
4
-1
5
-1

예제 입력 2

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

예제 출력 2

-1

힌트

The plots for the labyrinth and the first query of the first sample data are shown below.

(a) The labyrinth (b) One possible shortest path for the first query

Plots for sample test data