Сейф ЛТД. - это компания, производящая высококачественные сейфы. Ее последним изобретением был оптический механизм закрытия, который использует луч лазера, проходящего по прямоугольной сетке с несколькими зеркалами.
Когда лазер активируется, луч горизонтально входит в верхний ряд сетки с левой стороны. Луч отражается от каждого зеркала, в которое попадает. Каждое зеркало установлено под углом 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 если сейф нельзя открыть ни без вставки, ни со вставкой зеркала.