Безпечний вклад#3395

Безпечний вклад

3 секунди

256 мегабайтів

Дуже легка

Сейф ЛТД. — це компанія, яка виробляє високоякісні сейфи. Її останнім винаходом став оптичний механізм закриття, який використовує промінь лазера, що проходить по прямокутній сітці з декількома дзеркалами.

Коли лазер активується, промінь горизонтально входить у верхній ряд сітки з лівого боку. Промінь відбивається від кожного дзеркала, у яке потрапляє. Кожне дзеркало встановлено під кутом $45$ градусів у діагональному напрямку, або $/$ , або $\$ . Якщо промінь виходить із нижнього ряду сітки з правого боку, його виявляє детектор, і сейф відкривається (див. лівий рисунок зверху). Інакше сейф залишається зачиненим і звучить сигнал тривоги.

У кожному сейфі відсутнє одне дзеркало, що перешкоджає успішному проходженню лазерного променя через сітку (див. правий рисунок зверху). Сейф має механізм, який дозволяє користувачу поставити одне дзеркало у порожню клітинку сітки. Легітимний користувач знає правильне розташування і орієнтацію пропущеного дзеркала ( $/$ у рядку $4$ і колонці $3$ на рисунку зверху) і може відкрити сейф. Не знаючи цієї інформації, користувачу доведеться вгадувати розташування і орієнтацію дзеркала, що може виявитися складним завданням для великих сіток.

Вам потрібно визначити, чи є даний сейф дійсно безпечним. Безпечний сейф неможливо відкрити без вставки додаткового дзеркала, місце і орієнтація якого може визначатися неоднозначно. Дійсно, потрібних місць і орієнтацій може бути декілька.

Вхідні дані

Кожен тест описує один сейф і починається з рядка, який містить чотири цілих числа $r$ , $c$ , $m$ та $n$ ( $1 \leq r, c \leq 1000000$ 1 \leq r,\ c \leq 1000000 і $0 \leq m, n \leq 200000$ 0 \leq m,\ n \leq 200000). Механізм сітки складається з $r$ рядків та $c$ колонок. Кожен із наступних $m$ рядків містить два цілих числа $r_{i}$ r_i та $c_{i}$ c_i ( $1 \leq r_{i} \leq r$ 1 \leq r_i \leq r і $1 \leq c_{i} \leq c$ 1 \leq c_i \leq c), які задають $/$ дзеркало у рядку $r_{i}$ r_i та колонці $c_{i}$ c_i. Наступні $n$ рядків задають місцезнаходження $\$ дзеркал таким же способом. Усі $m + n$ m+n положень дзеркал попарно різні.

Вихідні дані

Для кожного тесту виведіть його номер та наступну інформацію:

0, якщо сейф відкривається без вставки дзеркала.
k r c, якщо сейф не можна відкрити без вставки дзеркала, причому існує рівно $k$ позицій, у яких дзеркало відкриває сейф, а ( $r, c$ ) — лексикографічно найменша (рядок, колонка). Позиція, у якій обидві орієнтації дзеркала ( $/$ і $\$ ) відкривають сейф, враховується один раз.
impossible, якщо сейф неможливо відкрити ні без вставки, ні зі вставкою дзеркала.

Приклади

Приклад 1