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

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

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

Формат выходных данных

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

Пример