Задача D. В какую группу? ≡

Условие

Межгалактический Институт Математики и Программирования набирает студентов. Все абитуриенты должны сдать два экзамена: по математике и информатике, после чего, исходя из результатов, их возьмут (или не возьмут) в одну из трех учебных групп, закреплённых за тремя кафедрами. Первая кафедра набирает в первую очередь студентов с высоким баллом по математике, вторая — по информатике, а третья предпочитает студентов, у которых баллы по информатике и математике меньше всего отличаются, даже если эти баллы низкие.

В день распределения руководители трех кафедр делают выбор по очереди, пока не разберут всех студентов.

Руководитель первой кафедры каждый раз берет студента с максимальным баллом по математике среди всех оставшихся, а если таких несколько — студента с максимальным баллом по информатике среди них.

Руководитель второй кафедры принимает студента с максимальным баллом по информатике, а если таких несколько — студента с максимальным баллом по математике среди них.

Руководитель третей кафедры берет студента с минимальной про модулю разницей баллов по этим двум экзаменам и, если этому условию удовлетворяют несколько студентов, то поступает в точности как руководитель первой кафедры.

Чтобы сократить время распределения студентов Вам требуется написать программу, которая зная баллы каждого студента по каждому из экзаменов распределит их по трем группам в требуемом порядке.

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

Входной файл содержит число N, за которым следует N пар целых чисел a_i b_i — баллы i-го абитуриента по математике и информатике соответственно. Гарантируется, что нет двух абитуриентов, у которых совпадают баллы по обоим экзаменам.

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

Выходной файл должен содержать N целых чисел — номера студентов в порядке их зачисления.

Ограничения

1 ≤ N ≤ 10⁵; 1 ≤ a_i, b_i ≤ 10⁶

Примеры тестов

1
1 1

1

3 
1 1 2 1 2 2

3 2 1