Собака, предатель и кабеля

Теперь у предателя есть собака! Палуба космического корабля может быть представлена в виде клетчатого поля $n\cdot m$, строки которого пронумерованы от $1$ до $n$ сверху вниз, а столбцы — от $1$ до $m$ слева направо. Между некоторыми соседними по стороне клетками располагаются отрезки кабеля.

В начале игры собака находится в клетке $(1,1)$, то есть в верхней левой клетке. Она выбирает одного из игроков, пусть выбранный игрок находится в клетке $(x,y)$. Собака выбирает один из кратчайших маршрутов от своего стартового положения до клетки $(x,y)$ (за один ход собака может переместиться из клетки в соседнюю по стороне). После чего, собака и игрок начинают по очереди делать ходы. Собака бежит по выбранному в самом начале маршруту, а игрок бежит ей навстречу по тому же маршруту с конца. Первый ход делает собака. Этот процесс продолжается до тех пор, пока собака и игрок не окажутся в одной клетке. Каждый раз, когда собака перебегает отрезок кабеля, она его перекусывает.

Помогите игрокам определить, какое максимальное количество отрезков кабеля может перекусить собака.

Входные данные

В первой строке дано три целых числа $n$, $m$ и $k(1\le n,m\le 200000,n\cdot m\le 200000,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$-ом случае.

Примеры

Ниже приведены расположения проводов в первом и во втором тестах.