Отслеживание RFID
Йерун управляет складом компании North Western Electrical Resource Company (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-координаты.