Відрізки на прямій повертаються
На прямій задано 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 - якщо такого не існує.
Якщо існує декілька розв'язків - виведіть довільний.