28639번 - Собака, предатель и кабеля 다국어

문제

Теперь у предателя есть собака! Палуба космического корабля может быть представлена в виде клетчатого поля $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),ドル на границе между которыми находится отрезок кабеля. Гарантируется, что клетки $(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) Во втором примере провода располагаются следующим образом