mos

Moș Crăciun a adus $N$ cadouri la cei $N$ copii care participă la concursul EMiCode Challenge. Copiii însă și-au schimbat cadoul dorit de la cel scris în scrisoare. Inițial, copilul $i$ dorea cadoul $i$, dar acum copilul $i$ dorește unul (oricare) din cadourile $L_i, L_i + 1, L_i + 2, \dots, R_i$. Moșul te-a rugat să îl ajuți să împartă cadourile astfel încât fiecare copil să primească un cadou dorit.

Cerință

Se dă $N$ -- numărul de copii și de cadouri și preferința de cadou a fiecărui copil sub forma de un interval $L_i, R_i$ de cadouri ($1 \leq L_i \leq R_i \leq N)$. Să se aleagă pentru fiecare copil $i$, un cadou $C_i$ astfel încât $C_i \in [L_i, R_i]$ și $C_i \neq C_j$, oricare ar fi $i \neq j$ (un cadou nu poate merge la mai mulți copii).

Deși nu ar fi întotdeauna posibil, datorită magiei Crăciunului se garantează că mereu se pot împărți cadourile astfel încât fiecare copil să primească un cadou din cele dorite.

Date de intrare

Pe prima linie a fișierului de intrare mos.in se află numărul $N$. Pe următoarele $N$ linii se află câte o pereche $L_i, R_i$ de numere, reprezentând preferința de cadouri a copilului $i$.

Date de ieșire

Să se afișeze în fișierul mos.out un șir $C_1, C_2, \dots, C_N$ de $N$ numere naturale de la $1$ la $N$ -- copilul $i$ va primi cadoul $C_i$.

Restricții și precizări

• $1 \le N \le 5 \ 000$;
• $1 \le L_i \le R_i \le N$.

Exemplu

mos.in

5
1 2
4 5
1 5
2 5
3 4

mos.out

1 4 2 5 3

Explicații

Primul copil a primit cadoul cu numărul $1 \in [1, 2]$.

Al doilea copil a primit cadoul numărul $4 \in [4, 5]$.

Al doilea cadou a fost primit de copilul numărul 3, iar $2 \in [1, 5]$.

Ultimul cadou l-a primit al patrulea copil, cu $5 \in [2, 5]$.

Iar ultimul copil a primit cadoul cu numărul $3 \in [3, 4]$.