28538번 - Trick or Treat! 스페셜 저지다국어

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

Поэтому дети решили собраться в группы, чтобы иметь больше шансов собрать конфеты. К сожалению, они не успели вовремя скоординироваться, поэтому каждый ребенок решил пойти в сторону ближайшего к нему другого ребенка. Разумеется, это не лучшая стратегия, ведь может так оказаться, что ребенок 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$-му.