The Dog, the Traitor, and the Cables

Now the traitor has a dog! The deck of a space ship is a grid of $n \times m$ cells. Rows are numbered from 1 to $n$ from top to bottom, and columns are numbered from 1 to $m$ from left to right. Some pairs of side-adjacent cells are separated by a cable segment.

At the start, the dog is in cell $(1, 1)$, the top left cell. It chooses one player, and let the chosen player be in cell $(x, y)$. The dog picks one of the shortest paths from its start to $(x, y)$ (in one move, the dog goes from a cell to a side-adjacent cell). Then the dog and the player take turns moving. The dog runs along the chosen path, and the player runs toward the dog from the other end of the same path. The dog moves first. The process continues until the dog and the player are in the same cell. Each time the dog crosses a cable segment, it bites through it.

Help the players find the maximum number of cable segments the dog can bite through.

The first line contains three integers $n$, $m$, and $k$, the size of the grid and the number of cable segments ($1 \le n, m \le 200\,000$; $n \cdot m \le 200\,000$, $0 \le k \le n \cdot (m - 1) + (n - 1) \cdot m$).

Each of the next $k$ lines describes one cable segment with 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 give the positions of two side-adjacent cells $(x_1, y_1)$ and $(x_2, y_2)$, and the cable segment lies on the border between them. It is guaranteed that the two cells are side-adjacent.

The next line contains one integer $q$, the number of player positions to answer for ($1 \le q \le 20$).

Each of the next $q$ lines contains two integers $x$ and $y$, the position of the player ($1 \le x \le n$, $1 \le y \le m$).

Print $q$ lines. The $i$-th line contains the maximum number of cable segments the dog can bite through in the $i$-th case.

(a) In the first input, the cables are placed as follows.

(b) In the second input, the cables are placed as follows.