Smaller on the left, smaller on the right

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

The competition organizers thought of an array \(a_i\) of \(n\) elements.

For each element, the value \(l_i\) is known — the number of smaller elements to the left of it, and \(r_i\) — the number of smaller elements to the right. Find any array that fits the given constraints.

For the given input data, it is guaranteed that at least one array exists. If there are multiple arrays that satisfy the conditions, output any of them.

Input

The first line contains a single integer \(n\) — the length of the array.

In the next \(n\) lines, 2 integers are given — \(l_i\) and \(r_i\).

Output

In a single line, output \(n\) numbers — the values of the array elements. All values must be within the range from 0 to \(10^9\).

If there are multiple arrays that satisfy the conditions, output any of them.

Constraints

\(1 \le n \le 10^5\),

\(0 \le l_i, r_i \le n-1\).

It is guaranteed that for the given input data, at least one array exists.

Samples