Цей пас пройде
Тесса — старшокласниця, яка грає у футбольній команді. Її тренери намагаються навчити команду техніці передачі м'яча, зокрема, розпізнавати моменти, коли товариш по команді відкритий для пасу. Вони вирішили змоделювати поле у вигляді квадратної сітки, як показано нижче. Кожен гравець (нападник або захисник) займає одну клітинку сітки — нападники позначені числами, а захисники — чорними колами. Кожен гравець захисту може переміститися в будь-яку сусідню клітинку, щоб перехопити пас; клітинки, які охороняють захисники, позначені X. Припустимо, що гравець 1 володіє м'ячем. Інший гравець вважається відкритим, якщо відрізок, що з'єднує центр квадрата цього гравця з центром квадрата гравця 1, не перетинає жодної з клітинок, до яких можуть дотягнутися захисники. Якщо відрізок торкається області захисника навіть в одній точці, пас може бути перехоплений. Нападники ніколи не блокують паси іншим нападникам.
У цьому прикладі гравець 1 може передати пас гравцю 2, але не гравцям 3 і 4.
Створивши таку модель, тренери раптом зрозуміли, що не вміють писати код, який здатний визначити, хто з гравців відкритий, а хто ні. Один з гравців повідомив їм Ваше ім'я як комп'ютерного генія, тому Вам доведеться все владнати.
Вхідні дані
Вхідні дані складаються з кількох тестів. Кожен тест починається з чотирьох натуральних чисел r c o d, що задають кількість рядків (r), колонок (c) на сітці та кількість нападників і захисників (o і d відповідно). Обидва r і c не перевищують 50. Кожен з наступних o рядків задає рядок і колонку — положення гравця нападу (рядки і колонки нумеруються з 0). Далі слідують аналогічні d рядків для гравців захисту. Нападники пронумеровані 1, 2, 3, ... у порядку, в якому вони подаються на вході, гравець нападу 1 володіє м'ячем. Жодні два гравці не знаходяться в одній клітинці сітки. Рядок з чотирма нулями завершує вхідні дані.
Вихідні дані
Для кожного тесту виведіть його номер і список гравців, яким гравець 1 може передати м'яч. Числа слід виводити у зростаючому порядку, розділяючи одним пробілом. Нумеруйте кожен тест, як показано в прикладі.