410630: GYM104067 E Trick or Treat!
Description
Одно из распространенных среди детей развлечений на Хэллоуин — наряжаться в костюмы и ходить выпрашивать собирать конфеты. Однако, в этом году что-то пошло не так, и на улицы вышло слишком много детей, поэтому конфет на всех может не хватить!
Поэтому дети решили собраться в группы, чтобы иметь больше шансов собрать конфеты. К сожалению, они не успели вовремя скоординироваться, поэтому каждый ребенок решил пойти в сторону ближайшего к нему другого ребенка. Разумеется, это не лучшая стратегия, ведь может так оказаться, что ребенок 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