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