410630: GYM104067 E Trick or Treat!

E. Trick or Treat!ограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Одно из распространенных среди детей развлечений на Хэллоуин — наряжаться в костюмы и ходить выпрашивать собирать конфеты. Однако, в этом году что-то пошло не так, и на улицы вышло слишком много детей, поэтому конфет на всех может не хватить!

Поэтому дети решили собраться в группы, чтобы иметь больше шансов собрать конфеты. К сожалению, они не успели вовремя скоординироваться, поэтому каждый ребенок решил пойти в сторону ближайшего к нему другого ребенка. Разумеется, это не лучшая стратегия, ведь может так оказаться, что ребенок A пошел в сторону ребенка B, а тот, в свою очередь, уже выдвинулся в сторону ребенка C. Но, будем надеяться, какие-то группы они все же смогут сформировать...

Всего на улицы Манхэттэна вышло $$$n$$$ детей, при чем $$$i$$$-й ребенок находится в точке с координатами $$$(x_i, y_i)$$$. Как известно, манхэттэнское расстояние между точками $$$(x_i, y_i)$$$ и $$$(x_j, y_j)$$$ равно $$$|x_i - x_j| + |y_i - y_j|$$$.

Чтобы предотвратить хаос на дорогах, вам поручено определить для каждого ребенка номер ближайшего к нему другого ребенка, чтобы иметь возможность хотя бы примерно предсказать траектории их перемещения по городу.

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

В первой строке ввода дано целое число $$$n$$$ — количество детей в городе ($$$2 \leqslant n \leqslant 10^5$$$).

В $$$i$$$-й из следующих $$$n$$$ строк через пробел даны два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-го ребенка ($$$0 \leqslant x_i, y_i \leqslant 10^9)$$$. Не гарантируется, что все дети находятся в разных точках — если два ребенка имеют одинаковые координаты, для них обоих кратчайшее расстояние будет равно $$$0$$$.

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

Выведите через пробел $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, $$$i$$$-е из которых равно номеру ребенка, ближайшего по манхэттэнскому расстоянию к $$$i$$$-му.

ПримерыВходные данные

3
1 1
3 3
6 6

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

2 1 2 

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

4
1 6
0 4
3 8
7 3

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

2 1 1 2