Відстеження RFID
Йерун керує складським приміщенням для зберігання товарів компанії North Western Electrical Resource Company (NWERC). Коли клієнт робить замовлення в NWERC, це замовлення передається на склад. Завдання Йеруна полягає в тому, щоб знайти замовлені продукти, упакувати їх у коробку та відправити клієнту.
NWERC має незвичайну політику складу: продукти не розміщені в певному порядку і розкидані по всьому приміщенню. Однак Йерун може виконувати свою роботу, оскільки кожен продукт відстежується за допомогою технології RFID. Зокрема, кожному продукту присвоюється бездротовий RFID-чіп, як тільки він потрапляє на склад, а датчики, розташовані на стелі складу, використовуються для автоматичного відстеження продуктів.
За замовчуванням кожен датчик має радіус дії r одиниць — тобто він може зчитувати будь-який RFID-чіп, розташований на відстані не більше r одиниць від нього по прямій лінії. Однак, якщо відрізок між датчиком і продуктом перетинає або торкається x стін, радіус дії датчика зменшується на x одиниць у цьому напрямку. Крім того, датчики можуть не зчитувати RFID-чіп через перешкоди від інших датчиків, тому відстань між будь-якою парою датчиків на складі гарантовано становить щонайменше r одиниць. Ви також можете припустити, що жоден датчик або продукт не розміщений на стіні.
Йерун тепер хоче визначити, для кожного продукту, які датчики можуть зчитувати його RFID-чіп. Чи можете ви йому допомогти?
Ілюстрація датчиків, стін і продуктів, як у прикладі вхідних даних.
Вхідні дані
На першому рядку одне додатне число: кількість тестових випадків, не більше 100. Після цього для кожного тестового випадку:
один рядок з чотирма цілими числами s (1 ≤ s ≤ 250000), r (1 ≤ r ≤ 20), w (0 ≤ w ≤ 10) і p (1 ≤ p ≤ 10000), де s представляє кількість датчиків, r радіус дії кожного датчика, w кількість стін і p кількість продуктів.
s рядків, що містять два цілі числа x_i і y_i (-10000 ≤ x_i, y_i ≤ 10000). Кожен такий рядок представляє датчик у місці (x_i, y_i). Відстань між будь-якою парою датчиків гарантовано становить щонайменше r одиниць.
w рядків, що містять чотири цілі числа bx_i, by_i, ex_i і ey_i (-10000 ≤ bx_i, by_i, ex_i, ey_i ≤ 10000). Кожен такий рядок представляє стіну, яку слід розглядати як відрізок прямої від (bx_i, by_i) до (ex_i, ey_i). Довжина цього відрізка буде позитивною.
p рядків, кожен з яких містить два цілі числа px_i і py_i (-10000 ≤ px_i, py_i ≤ 10000). Кожен такий рядок представляє продукт у місці (px_i, py_i).
Вихідні дані
Для кожного тестового випадку:
p рядків, кожен з яких представляє продукт у порядку, в якому вони з'являються у вхідних даних. Кожен рядок повинен містити ціле число t, кількість датчиків, які можуть відстежувати продукт; це число повинно бути потім доповнене списком з t упорядкованих пар, що представляють відповідні місця розташування датчиків. Якщо є кілька датчиків, вони повинні бути відсортовані у зростаючому порядку за x-координатою. Якщо кілька датчиків мають однакову x-координату, вони повинні бути відсортовані у зростаючому порядку за y-координатою.