Республиканская олимпиада по информатике 2008 год

Задача A. Манхэттенское расстояние

Ограничение по времени:

2 sec.

Ограничение по памяти:

128 MB.

На плоскости дано $N$ различных точек. Расстоянием между точками (x1, y1) и (x2, y2) будем считать $|x1 - x2| + |y1 - y2|$. Для каждой точки требуется найти одну из ближайших к ней точек.

Формат входного файла

Первая строка входного файла содержит целое число $N$ ($1$ < $N$ <= $10^5$). Следующие N строк содержат по два числа — координаты точек. Координаты — целые числа, по модулю не превышающие $10000$. Числа в строках разделены пробелами.

Формат выходного файла

Выходной файл должен содержать $N$ целых чисел, разделенных пробелом: i-е число есть номер одной из точек, ближайших к i-й. Точки нумеруются в том порядке, в котором они даны во входном файле, начиная с единицы.

Примеры:

Вход

4
0 0
1 1
0 1
1 0

Ответ

3 4 1 1