В одномерной стране есть n городов, i-й из которых расположен в точке xi и имеет население pi, причем как все xi, так и все pi попарно различны. Когда в одномерной стране появился интернет, было принято решение поставить главный сервер в самом крупном городе, а из каждого другого города j провести кабель в ближайший к нему город k, такой, что город k крупнее города j (в случае, если таких городов несколько, следовало выбрать более крупный). В этом случае город k назывался предком города j.
К сожалению, министерство связи одномерной страны слишком долго определяет, откуда и куда надо проводить кабели, а население страдает. Поэтому эту задачу придется решить вам. Определите для каждого города, какой город является его предком.
В первой строке содержится единственное целое число n (1 ≤ n ≤ 200000) — количество городов.
Каждая из следующих n строк содержит два целых числа через пробел xi и pi (1 ≤ xi, pi ≤ 109) — координата и население i-го города соответственно.
Выведите n целых чисел через пробел. i-е число должно быть равно номеру города, который является предком i-го города, или - 1, если у i-го города нет предка. Города нумеруются с единицы в порядке упоминания во входных данных.
4
1 1000
7 10
9 1
12 100
-1 4 2 1
3
1 100
2 1
3 10
-1 1 1
3
1 10
3 100
2 1
2 -1 2
