Dog, traitor and cable

Now the traitor has a dog! The deck of a spaceship can be represented as a checkered field $n\cdot m$, the rows of which are numbered from $1$ to $n$ from top to bottom, and the columns from $1$ to $m$ from left to right. Between some adjacent cells on the side there are cable segments.

At the start of the game, the dog is located in the cell $(1,1)$, i.e. the top left cell. It chooses one of the players, let the chosen player be in the cell $(x,y)$. The dog chooses one of the shortest routes from its starting position to the cell $(x,y)$ (in one move the dog can move from the cell to the adjacent side). After that, the dog and the player take turns making moves. The dog runs along the route chosen at the very beginning, and the player runs towards it along the same route from the end. The dog makes the first move. This process continues until the dog and the player are in the same cell. Every time the dog crosses a piece of cable, it bites it.

Help the players determine the maximum number of pieces of cable that a dog can bite into.

Input

The first line contains three integers $n,m$ and $k(1\le n,m\le 200000,n\cdot m\le 200000,0\le k\le n\cdot (m-1)+(n-1)\cdot m)$ — field dimensions and number of cable sections.

The following is a description of $k$ cable segments. Each segment is described by four integers $x_1,y_1,x_2$ and $y_2(1\le x_1,x_2\le n,1\le y_1,y_2\le m)$. These numbers define the positions of two adjacent cells $(x_1,y_1)$ and $(x_2,y_2)$, on the border between which there is a cable segment. It is guaranteed that cells $(x_1,y_1)$ and $(x_2,y_2)$ are side-adjacent.

The next line contains one integer $q(1\le q\le 20)$ — the number of positions of the players for which you want to calculate the answer.

The next $q$ lines contain two integers $x$ and $y(1\le x\le n,1\le y\le m)$ — the player's position.

Output

Print $q$ lines, the $i$-th line contains one number — the maximum number of cable segments that a dog can bite in the $i$-th case.

Examples

Below given the locations of the wires in the first and the second test cases.