eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кто ходит в гости по утрам

Кто ходит в гости по утрам

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В Чудесном Лесу живут N различных персонажей, у каждого из которых есть свой собственный домик. Следуя заветам одного из самых известных лесных персонажей, Винни-Пуха, каждый житель считает необходимым проснуться с утра пораньше, умыться, одеться и пойти в гости к кому-либо. Разумеется, чтобы поступить не просто мудро, а очень мудро и не потратить слишком много времени на дорогу, персонаж отправится не к кому-нибудь, а к своему соседу, то есть к тому из жителей, домик которого находится к данному персонажу на наименьшем возможном расстоянии. Нетрудно понять, что хозяина этого домика не окажется дома, поскольку он тоже воспользуется правилом Винни-Пуха. Лишь по этой причине некому будет ни крикнуть "Ура!", ни обрадоваться гостям. Если вдруг окажется, что несколько домиков расположены на минимальном расстоянии от персонажа, то он выберет для похода в гости домик с наименьшим номером. Ваша задача – определить какие персонажи соберутся у каждого домика.

Входные данные

В первой строке задается количество персонажей N (2N100000). В каждой из последующих N строк задаются по два числа – координаты точки на плоскости, в которой расположен домик соответствующего персонажа. Все координаты – целые неотрицательные числа, не превосходящие 10^9.

Выходные данные

Выведите N строк. i-ая строка должна содержать число i, за которым следует двоеточие и далее в порядке возрастания номера персонажей, которые придут в гости в i-ый домик.

Пример

Входные данные #1
6
0 0
1 0
0 1
3 3
2 2
3 1
Выходные данные #1
1: 2 3
2: 1
3:
4: 5
5: 4 6
6:
Автор Антон Лунёв
Источник Зимняя школа, Харьков 2011, День 6