Even after removing matrices forever, Ammar was still angry and asked the wizard to throw Ahmad in a new maze.
The maze this time is an infinite coordinates system with some cells containing walls and others empty. A cell $$$(x,y)$$$ is a block that Ahmad can't go to if $$$max(|x|,|y|)$$$ is odd.
You could notice that blocks will be in a shape of layers , so every layer has four walls : top, bottom, left, and right , and the center of the layers is an empty cell with coordinates $$$(0,0)$$$.
A wall can have at most one special block that Ahmad can use to go only from the inside of the layer to the outside; there are $$$m$$$ special blocks in the maze. Ahmad knows that only the first $$$n$$$ layers could contain special blocks, and the $$$n+1_{th}$$$ layer is always a complete wall.
In the image, $$$n=3$$$ and $$$m=4$$$. And the coordinates of the special blocks are $$$(-1,0) , (0,-1) , (3,-1)$$$ and $$$(-3,2)$$$.
As you know, Ahmad loves matrices. Ahmad is currently in cell $$$(S_x,S_y)$$$ and there is a matrix problem in cell $$$(G_x,G_y)$$$ , where both $$$S$$$ and $$$G$$$ are empty points. If Ahmad is currently in a cell, he could move up, down, left, or right and only into an empty cell or a special block(if he is inside the layer and going outside ). In other words, if he is in cell $$$(x,y)$$$ , he can move to $$$(x-1,y) , (x+1,y) , (x,y-1)$$$ or $$$(x,y+1)$$$.
Ahmad asks you to tell him what is the minimum path length that he could take to reach the matrix problem. You have to answer $$$q$$$ queries!
The first line contains three integers $$$n,m,q \: (1 \leq n,q \leq 10^5) (0 \leq m \leq 4 \cdot n)$$$ — the number of layers , the number of special blocks, and the number of queries.
Each of the next $$$m$$$ lines contains two integers $$$x,y \: (-2 \cdot n \leq x,y \leq 2 \cdot n)$$$ — the coordinates of the special blocks. It is guaranteed that all the special points are block cells ($$$max(|x|,|y|)$$$ is odd), $$$|x| \neq |y|$$$, and each wall contains at most one special block.
Each of the next $$$q$$$ lines contains 4 integers: $$$S_x, S_y, G_x, G_y \: (-2 \cdot n \leq S_x,S_y,G_x,G_y \leq 2 \cdot n)$$$ — Ahmad's current position and the matrix problem position. It is guaranteed that $$$max(|S_x|,|S_y|)$$$ and $$$max(|G_x|,|G_y|)$$$ are even (they are empty cells).
For each query, print the minimum length of a path that Ahmad could take to get to the matrix problem, or -1 if he can never reach it.
3 4 7-1 00 -13 -1-3 20 0 4 4-2 0 0 0-2 0 4 42 2 -4 -4-4 -4 4 44 4 6 6-6 0 6 0
12 -1 14 12 16 -1 24
