Центральная кофейня
Это обыкновенная причуда или всерьез и надолго? Вы не поверите, но постоянно растущее количество кофейных магазинов, которые открываются в вашем родном городе, становятся настоящей приманкой. Видимо люди настолько пристрастился к кофе, что стоимость арендной платы квартир, находящихся недалеко от многочисленных кофеен, является немного завышенной.
Этот факт заметила и местная компания, занимающаяся недвижимостью. Она заинтересована в выявлении наиболее ценных мест в городе с точки зрения их близости к большому количеству магазинов. Вам дали карту города, на которой обозначены все кофейни. Если предположить, что в среднем человек готов ходить только определенное количество кварталов за утренним кофе, Вам необходимо найти место, откуда можно попасть в наибольшее количество кофеен.
Как Вы уже догадались, город представляет собой прямоугольную сетку, стороны кварталов которого параллельны осям, проходящим с севера на юг и с востока на запад. Так как ходить разрешено только по улицам, то расстояние между пересечениями (a, b) и (c, d) равно |a - c|+|b - d|.
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест описывает город. Первая строка каждого теста содержит четыре целых числа dx, dy, n и q. Они задают размеры города dx×dy (1 ≤ dx, dy ≤ 1000), количество кофейных магазинов n (0 ≤ n ≤ 5·10^5), и число запросов q (1 ≤ q ≤ 20). Каждая из следующих n строк содержит два целых числа x_i и y_i (1 ≤ x_i ≤ dx, 1 ≤ y_i ≤ dy), задающих координаты расположения i-ой кофейни. На одном пересечении дорог может находиться не более одной кофейни. Каждая из следующих q строк содержит одно целое число m (0 ≤ m ≤ 10^6) - максимальное расстояние, которое человек согласен пройти чтобы выпить чашечку кофе.
Последний тест завершается строкой, содержащей четыре ноля.
Выходные данные
Для каждого теста вывести его номер. Для каждого запроса ответ следует выводить в отдельной строке. В каждой строке следует выводить максимальное количество кофейных магазинов, достижимых для заданного расстояния m, за которым должны следовать координаты оптимального расположения. В примере показано, что 3 кофейных магазина достижимы при расстоянии 1 из точки (3, 4), 4 магазина достижимы при расстоянии 2 из точки (2, 2), и 5 магазинов достижимы при расстоянии 4 из точки (3, 1). Если существует несколько оптимальных местоположений, то вывести следует самое южное (с наименьшей положительной y-координатой). Если и в этом случае существует несколько оптимальных местоположений, то следует выбрать самое западное (с наименьшей положительной x-координатой).
Формат выходных данных указан в примере.