Отрезки на прямой возвращаются
На прямой задано N попарно различных отрезков [a_i, b_i] (i = 1, 2, ..., N, a_i < b_i). Будем говорить, что отрезок номер i непосредственно содержится в отрезке номер j (i ≠ j), если:
он полностью принадлежит j-му (то есть a_j ≤ a_i и b_i ≤ b_j);
среди заданных N отрезков не найдётся такого отрезка (с номером k), что i-й отрезок принадлежит k-му и k-й принадлежит j-му (здесь i, j и k - различные числа).
Ваша задача - для каждого из заданных отрезков найти тот, в котором он непосредственно содержится, либо сообщить, что таких нет. Если данный отрезок непосредственно содержится сразу в нескольких - подходит любой из них.
Входные данные
Сначала вводится целое число N (1 ≤ N ≤ 100000). Далее идут N пар целых чисел a_i, b_i (-10^9 ≤ a_i < b_i ≤ 10^9).
Выходные данные
Выведите N чисел. Число номер i должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер i, либо 0 - если такого не существует.
Если существует несколько решений - выведите любое.