Республиканская олимпиада по информатике 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