개, 배신자, 그리고 케이블

이제 배신자에게도 개가 있다! 우주선 갑판은 $n \times m$ 격자 칸으로 이루어져 있다. 행은 위에서 아래로 1부터 $n$까지, 열은 왼쪽에서 오른쪽으로 1부터 $m$까지 번호가 매겨진다. 변을 공유하는 이웃 칸 사이 일부에는 케이블 조각이 놓여 있다.

게임 시작 시 개는 왼쪽 위 칸 $(1, 1)$에 있다. 개는 플레이어 한 명을 고르며, 그 플레이어가 $(x, y)$ 칸에 있다고 하자. 개는 시작 칸에서 $(x, y)$까지 가는 최단 경로 중 하나를 고른다. (개는 한 번에 변을 공유하는 이웃 칸으로 한 칸 움직인다.) 그다음 개와 플레이어가 번갈아 움직인다. 개는 고른 경로를 따라 달리고, 플레이어는 같은 경로의 반대쪽 끝에서 개를 향해 달린다. 첫 이동은 개가 한다. 개와 플레이어가 같은 칸에 놓이면 과정이 끝난다. 개가 케이블 조각을 지날 때마다 그 케이블을 물어 끊는다.

플레이어들이 개가 끊을 수 있는 케이블 조각의 최대 개수를 구하도록 도와라.

첫 줄에 정수 $n$, $m$, $k$가 주어진다. 각각 격자의 크기와 케이블 조각의 개수이다($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$).

다음 $k$줄에는 케이블 조각이 네 정수 $x_1$, $y_1$, $x_2$, $y_2$로 하나씩 주어진다($1 \le x_1, x_2 \le n$; $1 \le y_1, y_2 \le m$). 두 칸 $(x_1, y_1)$과 $(x_2, y_2)$는 변을 공유하는 이웃 칸이며, 케이블 조각은 두 칸 사이의 경계 위에 있다. 이 조건은 항상 보장된다.

다음 줄에는 정수 $q$가 주어진다. 답을 구할 플레이어 위치의 개수이다($1 \le q \le 20$).

다음 $q$줄에는 플레이어의 위치 $x$, $y$가 주어진다($1 \le x \le n$, $1 \le y \le m$).

$q$줄을 출력한다. $i$번째 줄에는 $i$번째 경우에 개가 끊을 수 있는 케이블 조각의 최대 개수를 출력한다.

(a) 첫 번째 입력에서 케이블은 다음과 같이 놓여 있다.

(b) 두 번째 입력에서 케이블은 다음과 같이 놓여 있다.