Задачі
Безпечний вклад
Безпечний вклад
Сейф ЛТД. - це компанія, яка виробляє високоякісні сейфи. Її осстаннім винаходом був оптичний механізм закриття, який використовує промінь лазера, що проходить по прямокутній сітці з декількома дзеркалами.
\includegraphics{https://static.e-olymp.com/content/af/afbeae2bd6997fbdb4b3206d5859a82164f4d7fd.jpg}
Коли лазер активується, промінь горизонтально входить у верхній ряд сітки з лівої сторони. Промінь відбивається від кожного дзеркала, у яке потрапляє. Кожне дзеркало встановлено під кутом \textbf{45} градусів у діагональному напрямку, або \textbf{/} або \textbf{\textbackslash}. Якщо промінь виходить з нижнього рядка сітки з правої стороны, то він виявляється детектором і сейф відкривається (див. лівий рисунок зверху). Інакше сейф залишається зачиненим і звучить сигнал тревоги.
У кожному сейфі відсутнє одне дзеркало, яке попереджує успішне проходження лазерного променя через сітку (див. правий рисунок зверху). Сейф має механізм, який дозволяє користувачу поставити одне дзеркало у порожню клітинку сітки. Законий користувач знає коректне розміщення і орієнтацію пропущеного дзеркала (\textbf{/} у рядку \textbf{4} і колонці \textbf{3} на рисунку зверху) і може відкрити сейф. Не знаючи цієї інформації, користувачу прийдеться вгадувати розміщення і орієнтацію дзеркала, що може виявитись складною задачею для великих сіток.
Вам потрібно встановити, чи є заданий сейф дійсно безпечним. Безпечний сейф не можна відчинити, не вставивши додадкове дзеркало, місце і орієнтація якого може визначатись неоднозначно. Дійсно, потрібних місць і орієнтацій може бути декількі.
\InputFile
Кожен тест описує один сейф і починається з рядка, який містить чотири цілих числа \textbf{r}, \textbf{c}, \textbf{m} та \textbf{n} (\textbf{1 }≤ \textbf{r}, \textbf{c }≤ \textbf{1000000 і} \textbf{0 }≤ \textbf{m}, \textbf{n }≤ \textbf{200000}). Механізм сітки складається з \textbf{r }рядків та \textbf{c} колонок. Кожен з наступних \textbf{m} рядків містить два цілих числа \textbf{r_i} та \textbf{c_i} (\textbf{1 }≤ \textbf{r_i} ≤ \textbf{r} і \textbf{1 }≤ \textbf{c_i} ≤ \textbf{c}), які задають \textbf{/} зеркало у рядку \textbf{r_i} та колонці \textbf{c_i}. Наступні \textbf{n }рядків задають місцезнаходження \textbf{\textbackslash} дзеркал таким же способом. Усі \textbf{m + n }положень дзеркал попарно різні.
\OutputFile
Для кожного тесту вивести його номер та наступну інформацію:
\begin{itemize}
\item \textbf{0} якщо сейф відкривається без вставки дзеркала.
\item \textbf{k r c} якщо сейф не можна відкрити не вставивши дзеркало, причому для відкриття сейфу існує у точності \textbf{k} позицій для нього, а (\textbf{r}, \textbf{c}) - лексикографічно найменша (рядок, колонка). Позиція, у якій обидва положення дзеркала - і \textbf{/} і \textbf{\textbackslash} відкриває сейф, вважається за одну.
\item \textbf{impossible} якщо сейф не можна відкрити ні без вставки, ні зі вставкою дзеркала.
\end{itemize}
Вхідні дані #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