Безпечний вклад
Сейф ЛТД. - це компанія, яка виробляє високоякісні сейфи. Її осстаннім винаходом був оптичний механізм закриття, який використовує промінь лазера, що проходить по прямокутній сітці з декількома дзеркалами.
Коли лазер активується, промінь горизонтально входить у верхній ряд сітки з лівої сторони. Промінь відбивається від кожного дзеркала, у яке потрапляє. Кожне дзеркало встановлено під кутом 45 градусів у діагональному напрямку, або / або \. Якщо промінь виходить з нижнього рядка сітки з правої стороны, то він виявляється детектором і сейф відкривається (див. лівий рисунок зверху). Інакше сейф залишається зачиненим і звучить сигнал тревоги.
У кожному сейфі відсутнє одне дзеркало, яке попереджує успішне проходження лазерного променя через сітку (див. правий рисунок зверху). Сейф має механізм, який дозволяє користувачу поставити одне дзеркало у порожню клітинку сітки. Законий користувач знає коректне розміщення і орієнтацію пропущеного дзеркала (/ у рядку 4 і колонці 3 на рисунку зверху) і може відкрити сейф. Не знаючи цієї інформації, користувачу прийдеться вгадувати розміщення і орієнтацію дзеркала, що може виявитись складною задачею для великих сіток.
Вам потрібно встановити, чи є заданий сейф дійсно безпечним. Безпечний сейф не можна відчинити, не вставивши додадкове дзеркало, місце і орієнтація якого може визначатись неоднозначно. Дійсно, потрібних місць і орієнтацій може бути декількі.
Вхідні дані
Кожен тест описує один сейф і починається з рядка, який містить чотири цілих числа r, c, m та n (1 ≤ r, c ≤ 1000000 і 0 ≤ m, n ≤ 200000). Механізм сітки складається з r рядків та c колонок. Кожен з наступних m рядків містить два цілих числа r_i та c_i (1 ≤ r_i ≤ r і 1 ≤ c_i ≤ c), які задають / зеркало у рядку r_i та колонці c_i. Наступні n рядків задають місцезнаходження \ дзеркал таким же способом. Усі m + n положень дзеркал попарно різні.
Вихідні дані
Для кожного тесту вивести його номер та наступну інформацію:
0 якщо сейф відкривається без вставки дзеркала.
k r c якщо сейф не можна відкрити не вставивши дзеркало, причому для відкриття сейфу існує у точності k позицій для нього, а (r, c) - лексикографічно найменша (рядок, колонка). Позиція, у якій обидва положення дзеркала - і / і \ відкриває сейф, вважається за одну.
impossible якщо сейф не можна відкрити ні без вставки, ні зі вставкою дзеркала.