Problem E
Micro-Row

You are studying $N$ microbes. The $i^\text {th}$ microbe has initial x-coordinate $P_ i$ nanometers and will travel $S_ i$ nanometers in the positive x-direction each second.

All these x-coordinates are initially distinct. You know that these microbes are incredibly amorphous, so that if one of them touches another one (that is, they occupy the exact same x-coordinate at the same time) they will merge together, ruining the whole study. To this end, you want to separate the microbes into rows (where each row has a distinct y-coordinate) before the study begins, such that no two microbes will ever touch each other, no matter how long you observe them.

It is hard to keep track of too many rows, so you want to minimize the total number of rows you have to separate the microbes into. How should you separate these microbes such that the minimum number of rows is needed?

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 200\, 000$), the number of microbes.

The next $N$ lines of input contain the descriptions of the microbes. In particular, the $i^\text {th}$ of these lines contains two integers $P_ i$ ($1\leq P_ i \leq 10^9$; $P_ i \neq P_ j$ for $i \neq j$) and $S_ i$ ($1 \leq S_ i \leq 10^9$), denoting that the $i^\text {th}$ microbe has initial x-coordinate $P_ i$ nanometers and will travel $S_ i$ nanometers in the positive x-direction each second.

Output

Output a single line containing $N$ distinct integers $r_1, r_2, \dots , r_ N$ ($1 \leq r_ i \leq N$), the rows the microbes should be located. There must be at least one microbe on each row; that is, $r_ i = k$ for some $k$ implies, for all positive integer $k’ < k$, the existence of some $j$ such that $r_ j = k’$. The configuration you provide should not allow any two microbes to touch each other at any point, and, among all such configurations satisfying that criteria, use the minimum possible number of rows.

If there are multiple correct answers, you can output any of them.

5
6 1
1 3
3 4
5 6
12 8

1 2 2 2 1