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) Во втором примере провода располагаются следующим образом