Endless Road

Whenever KAIST students leave campus, they usually walk along a straight road called the Endless Road. Many students feel the road never ends, partly because the scenery along it is dull. We model the Endless Road as a straight line of length $10^9$. A position on the line is a real number $x \in [0, 10^9)$.

The members of RUN@KAIST decided to plant flowers of different colors along the road to liven it up. There are $N$ members, numbered from $1$ to $N$. At the last regular meeting, each member $i$ was assigned a nonempty segment $[L_i, R_i)$ on the line, which contains every position $x$ with $L_i \le x < R_i$.

A member with a higher index carries more responsibility in the club, so the segment length does not decrease as the index grows: $R_i - L_i \le R_j - L_j$ for all $1 \le i < j \le N$.

Flower planting takes place in $N$ turns. In each turn, one member who has not been selected yet plants flowers. The selected member plants flowers over their segment $[L_i, R_i)$, except at positions where other members have already planted flowers.

The next member is chosen as follows. The member who would plant the fewest flowers at that moment goes first. The amount planted is the length of the part of the segment where the member plants new flowers, and this length may be zero. If several members tie, the member with the smallest index goes first.

Jaeung must announce the planting schedule. Find the order in which all $N$ members plant flowers under these rules.

The first line contains an integer $N$. Each of the next $N$ lines contains two integers $L_i$ and $R_i$.

Print $N$ space-separated integers. The $i$-th integer is the index of the member who plants flowers in the $i$-th turn.

$1 \leq N \leq 250\,000$. $0 \le L_i < R_i \le 10^9$. $R_i - L_i \leq R_j - L_j$ for all $1 \le i < j \le N$. All intervals are distinct, that is, $(L_i, R_i) \neq (L_j, R_j)$ for all $1 \le i < j \le N$.