Теперь у предателя есть собака! Палуба космического корабля может быть представлена в виде клетчатого поля $n \cdot m$, строки которого пронумерованы от $1$ до $n$ сверху вниз, а столбцы --- от $1$ до $m$ слева направо. Между некоторыми соседними по стороне клетками располагаются отрезки кабеля. В начале игры собака находится в клетке $(1, 1)$, то есть в верхней левой клетке. Она выбирает одного из игроков, пусть выбранный игрок находится в клетке $(x, y)$. Собака выбирает один из кратчайших маршрутов от своего стартового положения до клетки $(x, y)$ (за один ход собака может переместиться из клетки в соседнюю по стороне). После чего, собака и игрок начинают по очереди делать ходы. Собака бежит по выбранному в самом начале маршруту, а игрок бежит ей навстречу по тому же маршруту с конца. Первый ход делает собака. Этот процесс продолжается до тех пор, пока собака и игрок не окажутся в одной клетке. Каждый раз, когда собака перебегает отрезок кабеля, она его перекусывает. Помогите игрокам определить, какое максимальное количество отрезков кабеля может перекусить собака. \InputFile В первой строке дано три целых числа $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)$ --- позиция игрока. \OutputFile Выведите $q$ строк. В $i$-ой строке выведите одно число --- максимальное количество отрезков кабеля, которое может перекусить собака в $i$-ом случае. \Examples Ниже приведены расположения проводов в первом и во втором тестах. \includegraphics{https://static.eolymp.com/content/47/47d7909f0c35d70a49ec3a67791d505142242b28.gif}