Вот и наступил апрель. На улице набухают первые почки. Снег уже почти везде растаял. За окном все чаще и чаще раздаётся заливное щебетание птиц. Лишь на матмехе УрГУ стало видно меньше студентов. Да и в общаге совсем не видно привычных обитателей — тараканов.
«С чем связаны эти явления?» — спросите вы.
Скоро начнётся празднование Дня Математика и Механика. А вместе с ним в УрГУ будут проведены традиционные тараканьи бега. Вот и заняты все студенты сейчас тем, что тренируют своих любимцев. Каждый хочет, чтобы именно его питомец стал главным призёром соревнований и получил гордое имя «Магаз».
Правила соревнований немного необычны. Каждый круг в N точках выкладывается некоторая сладость. И одновременно к сладостям запускается M тараканов. N тараканов, добежавших первыми до сладостей, переходят в следующий тур.
Во время забега все зрители имеют уникальную возможность сделать ставки и выиграть кучу денег. Но вот организаторам
тотализатора пока не весело, они не могут понять, как правильно и оперативно организовать учёт вероятностей выигрыша тараканов, чтобы получить от мероприятия максимальную прибыль. К тому же матмех — факультет не маленький, и все хотят поучаствовать.
Вам предлагается для каждого кусочка сладости найти ближайшего к нему таракана и выявить тем самым всех явных лидеров забега.
Исходные данные
В первой строке дано целое число M (1 ≤ M ≤ 100000). Далее следуют M строк, содержащих координаты тараканов в настоящий момент. (M + 2)-я строка содержит целое число N (0 ≤ N ≤ 10000). Далее в N строках записаны координаты кусочков сладости. Все координаты — действительные числа (−10000.0 ≤ x, y ≤ 10000.0). Расстояние между любыми двумя тараканами составляет не менее 10−3. Также расстояние между любыми двумя кусочками составляет не менее 10−3.
Результат
Для каждого кусочка сладостей выведите через пробел номера тараканов, ближайших к нему, в порядке по возрастанию номеров.
Пример
исходные данные | результат |
---|
4
0 0
1 0
0 1
1 2
2
0 0
0 2
| 1
3 4
|
Автор задачи: Ден Расковалов
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005 г.