Кто ходит в гости по утрам
Кто ходит в гости по утрам
В Чудесном Лесу живут N различных персонажей, у каждого из которых есть свой собственный домик. Следуя заветам одного из самых известных лесных персонажей, Винни-Пуха, каждый житель считает необходимым проснуться с утра пораньше, умыться, одеться и пойти в гости к кому-либо. Разумеется, чтобы поступить не просто мудро, а очень мудро и не потратить слишком много времени на дорогу, персонаж отправится не к кому-нибудь, а к своему соседу, то есть к тому из жителей, домик которого находится к данному персонажу на наименьшем возможном расстоянии. Нетрудно понять, что хозяина этого домика не окажется дома, поскольку он тоже воспользуется правилом Винни-Пуха. Лишь по этой причине некому будет ни крикнуть "Ура!", ни обрадоваться гостям. Если вдруг окажется, что несколько домиков расположены на минимальном расстоянии от персонажа, то он выберет для похода в гости домик с наименьшим номером. Ваша задача – определить какие персонажи соберутся у каждого домика.
Входные данные
В первой строке задается количество персонажей N (2 ≤ N ≤ 100000). В каждой из последующих N строк задаются по два числа – координаты точки на плоскости, в которой расположен домик соответствующего персонажа. Все координаты – целые неотрицательные числа, не превосходящие 10^9.
Выходные данные
Выведите N строк. i-ая строка должна содержать число i, за которым следует двоеточие и далее в порядке возрастания номера персонажей, которые придут в гости в i-ый домик.
Пример
6 0 0 1 0 0 1 3 3 2 2 3 1
1: 2 3 2: 1 3: 4: 5 5: 4 6 6: