Пес, зрадник і кабель#11079
Тепер у зрадника є собака! Палуба космічного корабля представлена у вигляді клітинкового поля розміром n \cdot 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) — розміри поля і кількість відрізків кабелю.
Далі йде опис відрізків кабелів. Кожен відрізок описується чотирма цілими числами 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) — кількість положень гравців, для яких потрібно обчислити відповідь.
У наступних рядках дано по два цілих числа і y\:(1 \le x \le n, 1 \le y \le m) — позиція гравця.
Виведіть рядків. У -му рядку виведіть одне число — максимальну кількість відрізків кабелю, яку може перекусити собака в -му випадку.
Нижче наведені розташування проводів у першому і другому тестах.
Приклад 1
Приклад 2