Собака, зрадник і кабель

Тепер у зрадника є собака! Палуба космічного корабля представлена у вигляді клітинкового поля розміром $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$-му випадку.

Приклади

Нижче наведені розташування проводів у першому і другому тестах.