Description

Little T has planned the exhibition area as an $n \times n$ two-dimensional grid. The outermost perimeter of the grid is surrounded by a ring of exhibition walls, meaning all cells with a coordinate equal to $0$ or $n+1$ are exhibition wall cells. Additionally, there are $m$ exhibition wall cells scattered inside the exhibition area, where the $i$-th ($1 \le i \le m$) cell has coordinates $(x_i, y_i)$. It is guaranteed that all exhibition wall cells are 4-connected.

After field testing, Little T summarized the time consumption rules for moving between cells. Specifically, there are two ways to move between cells: Moving one cell in the up, down, left, or right direction, i.e., from $(x, y)$ to one of the adjacent cells $(x-1, y), (x+1, y), (x, y-1), (x, y+1)$, consumes $2$ units of time. Moving one cell in the diagonal direction, i.e., from $(x, y)$ to one of the diagonal cells $(x-1, y-1), (x-1, y+1), (x+1, y-1), (x+1, y+1)$, consumes $3$ units of time.

Of course, the target cell of a move cannot be an exhibition wall cell. Note: When moving in a diagonal direction, you can pass directly through the gap between two diagonal exhibition wall cells. For example, even if both $(x, y+1)$ and $(x+1, y)$ are exhibition wall cells, you can still consume $3$ units of time to move directly from $(x, y)$ to $(x+1, y+1)$.

Little S has placed a total of $q$ treasures in the exhibition area. For the $i$-th ($1 \le i \le q$) treasure, she announces its location $(tx_i, ty_i)$, and your current location is $(sx_i, sy_i)$. To obtain each treasure as quickly as possible, you need to calculate the minimum time required to move from your current location to the treasure's location.

Input

The first line contains three positive integers $n, m, q$ ($1 \le n \le 10^5, 1 \le m, q \le 3 \times 10^5$).

The next $m$ lines each contain two positive integers $x_i, y_i$ ($1 \le x_i, y_i \le n$), representing the coordinates of the $i$-th exhibition wall cell. It is guaranteed that all $(x_i, y_i)$ are distinct.

The next $q$ lines each contain four positive integers $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$), representing your current location and the treasure's location for the $i$-th treasure. It is guaranteed that $(sx_i, sy_i)$ and $(tx_i, ty_i)$ are not exhibition wall cells.

Output

Output $q$ lines, each containing an integer representing the answer. Specifically, if you cannot move to the treasure's location, output $-1$.

Examples

Input 1

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

Output 1

2
16
11
10
11

Note 1

For the second treasure, you can move along the following path: $(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$, with a total time consumption of $2 + 3 + 3 + 3 + 2 + 3 = 16$.