Evil Problemsetters

Some contestants decide to escape from this contest because of the challenging problems. To stop them, the EVIL problem setters built a labyrinth at the stadium's exit. The labyrinth is an $n \times m$ grid with an entrance, an exit, and $k$ black holes. A contestant who accidentally steps into a black hole falls into it and can never escape from the contest.

Worse, the problem setters may change the coordinates of the entrance and the exit. You are a poor contestant who starts at the entrance and wants to reach the exit without stepping into any black hole. Each step moves you to one of the four adjacent cells. After each time the problem setters change the coordinates of the entrance and the exit, find the minimum number of steps needed to get from the entrance to the exit.

The first line 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)$, the number of rows, the number of columns, the number of black holes, and the number of queries.

The next $k$ lines describe the black holes. Each line contains two integers $x, y$ $(1 \leq x \leq n, 1 \leq y \leq m)$, the coordinates of a black hole. No two black holes share a position.

The last $q$ lines describe the queries. Each line 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 entrance and $(x_t, y_t)$ is the exit.

For each query, print the minimum number of steps needed to get from the entrance to the exit, one per line. If the exit cannot be reached, print $-1$. If the entrance or the exit is at the same position as a black hole, the exit is considered unreachable.

The layout of the labyrinth and one possible shortest path for the first query of the first sample are shown below.