There is an $$$(n+2) \times (n+2)$$$ grid, where both coordinates range from $$$0$$$ to $$$n+1$$$ inclusive. The outermost cells of the grid are all obstacle cells.

In addition, there are $$$m$$$ more obstacle cells in the grid. The $$$i$$$-th obstacle cell is located at $$$(x_i, y_i)$$$. It is guaranteed that all obstacles (including the outer boundary cells) are 4-connected. That is, you can move between any two obstacle cells by moving up, down, left, or right through other obstacle cells.

Little L is walking in this maze. He cannot step into any obstacle cell at any time. If Little L is at position $$$(x, y)$$$, he can make the following moves:

Move orthogonally to an adjacent cell $$$(x+1,y)$$$, $$$(x-1,y)$$$, $$$(x,y+1)$$$, or $$$(x,y-1)$$$ with a cost of $$$2$$$.
Move diagonally to an adjacent cell $$$(x+1,y+1)$$$, $$$(x+1,y-1)$$$, $$$(x-1,y+1)$$$, or $$$(x-1,y-1)$$$ with a cost of $$$3$$$.

There are $$$q$$$ queries. For each query, you are given a starting point and an ending point. You need to find the minimum total cost for Little L to travel from the starting point to the ending point. If it is impossible to reach the ending point, output $$$-1$$$.

Input

The first line of the input contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m, q \le 3 \cdot 10^5$$$).

The next $$$m$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of the $$$i$$$-th obstacle cell. It is guaranteed that all obstacle coordinates are distinct, and that all obstacles (including the outer boundary cells) are 4-connected.

The next $$$q$$$ lines each contain four integers $$$s_x$$$, $$$s_y$$$, $$$t_x$$$, and $$$t_y$$$ — a query with starting point $$$(s_x, s_y)$$$ and ending point $$$(t_x, t_y)$$$. It is guaranteed that neither $$$(s_x,s_y)$$$ nor $$$(t_x,t_y)$$$ is an obstacle.

Output

For each query, output a single integer — the minimum cost to travel from the starting point to the ending point. Or print $$$-1$$$ if it is impossible to do so.

Note

For the second query, you can move as follows: $$$(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$$$. The total cost is $$$2 + 3 + 3 + 3 + 2 + 3 = 16$$$.

Maze

Examples