e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

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

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

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

prb3395

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

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

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

Вхідні дані

Кожен тест описує один сейф і починається з рядка, який містить чотири цілих числа r, c, m та n (1 r, c 1000000 і0 m, n 200000). Механізм сітки складається з r рядків та c колонок. Кожен з наступних m рядків містить два цілих числа ri та ci (1 rir і 1 cic), які задають / зеркало у рядку ri та колонці ci. Наступні n рядків задають місцезнаходження \ дзеркал таким же способом. Усі m + n положень дзеркал попарно різні.

Вихідні дані

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

  • 0 якщо сейф відкривається без вставки дзеркала.
  • k r c якщо сейф не можна відкрити не вставивши дзеркало, причому для відкриття сейфу існує у точності k позицій для нього, а (r, c) - лексикографічно найменша (рядок, колонка). Позиція, у якій обидва положення дзеркала - і / і \ відкриває сейф, вважається за одну.
  • impossible якщо сейф не можна відкрити ні без вставки, ні зі вставкою дзеркала.
    Ліміт часу 3 секунди
    Ліміт використання пам'яті 256 MiB
    Вхідні дані #1
    5 6 1 4
    2 3
    1 2
    2 5
    4 2
    5 5
    100 100 0 2
    1 77
    100 77
    100 100 0 0
    
    Вихідні дані #1
    Case 1: 2 4 3
    Case 2: 0
    Case 3: impossible