Менші зліва, менші справа

Limits: 2 sec., 512 MiB

Організатори змагань загадали масив $a_i$ з $n$ елементів.

Для кожного елемента відомо значення $l_i$ — кількість менших елементів зліва від нього та $r_i$ — кількість менших елементів справа. Знайдіть будь-який масив, який підходить під дані обмеження.

Для заданих вхідних даних гарантовано існує хоча б один масив. Якщо існує декілька масивів, які задовільняють умови, виведіть будь-який з них.

Input

У першому рядку задано єдине ціле число $n$ — довжину масиву.

У наступних $n$ рядках задано по 2 цілих числа — $l_i$ та $r_i$.

Output

У єдиному рядку виведіть $n$ чисел — значення елементів масиву. Усі значення повинні бути в межах від 0 до $10^9$.

Якщо існує декілька масивів, які задовільняють умови, виведіть будь-який з них.

Constraints

$1 \le n \le 10^5$,

$0 \le l_i, r_i \le n-1$.

Гарантується, що для заданих вхідних даних існує хоча б один масив.

Samples