Problem Description

The "Gravity Ball" game is played on an $n \times n$ square area. Denote the cell in the $i$-th row from top to bottom and the $j$-th column from left to right as $(i, j)$.

There are $m$ obstacles in the square area. The $i$-th obstacle occupies position $(x_i, y_i)$. In addition, everything outside the boundary of the square area is considered an obstacle.

Now there are two balls located at $(a, b)$ and $(c, d)$. In the game, you can perform the following operation:

• Choose one direction from up, down, left, and right, and "switch" the direction of gravity to that direction. Then the two balls will move simultaneously in that direction until they hit an obstacle.

You need to use the minimum number of operations to make the two balls reach the same position.

There are $q$ rounds of the game. In each round, only the initial positions of the balls are different, while the obstacle positions remain unchanged. You need to find the minimum number of operations for each round, or report that there is no solution.

Input Format

The first line contains three integers $n, m, q$, representing the size of the square area, the number of obstacles, and the number of game rounds.

The next $m$ lines each contain two integers $x_i, y_i$, indicating that there is an obstacle at position $(x_i, y_i)$. The data guarantees that all obstacle positions are distinct.

The next $q$ lines each contain four integers $a, b, c, d$, indicating the initial positions of the two balls in a round. It is guaranteed that the initial positions do not contain obstacles.

Output Format

Output $q$ lines in total. On the $i$-th line, output one integer representing the minimum number of operations needed for the $i$-th round. If there is no solution, output -1.

4 4 3
2 2
2 4
3 2
4 4
1 3 4 3
2 1 2 1
1 2 3 4

1
0
3

Hint

Sample $1$ Explanation

In this sample, the obstacles are distributed as the red crosses in the figure.

In the first query, you only need to change gravity upward (or downward) to make the two balls arrive at the same time.

In the second query, the two balls are already at the same position, so no operation is needed.

In the third query, change the direction of gravity $3$ times, in order: left, down, left. The movement paths of the balls are shown as the pink, orange, and brown lines in the figure:

Constraints and Notes

For $20\%$ of the testdata: $n, m \le 2$.

For $50\%$ of the testdata: $n, m \le 30$.

For the other $30\%$ of the testdata: $q = 1$.

For $100\%$ of the testdata: $1 \le n, m \le 250$, $1 \le q \le 10^5$, $1 \le x_i, y_i, a, b, c, d \le n$.

The testdata is provided by SSerxhs.

The testdata references the construction idea from Problem A of the 2020 ICPC Regional Contest (Nanjing), "Xiaomiaomiao Dislikes Computational Geometry", and we would like to express our thanks here.

Translated by ChatGPT 5