Given $N$ intervals $[L_i, R_i)$ on a number line, which are distinct and have non-decreasing lengths, i.e., for $1 \le i < j \le N$, $R_i - L_i \le R_j - L_j$ is guaranteed, and it is not the case that $L_i = L_j$ and $R_i = R_j$ simultaneously.

Initially, the number line is white. Perform $N$ operations. In each operation, choose an interval $[L_i, R_i)$ that has not been chosen before and color it black. The goal is to minimize the total length of the black-colored portion after all operations are completed. If there are multiple choices that result in the same total length, choose the one with the smallest index. Find the index of the interval chosen in each operation.

Input

The first line contains a positive integer $N$.

The following $N$ lines each contain two non-negative integers $L_i, R_i$.

Output

A single line containing $N$ positive integers, where the $i$-th integer represents the index of the interval chosen in the $i$-th operation.

Examples

Input 1

6
1 2
2 3
3 4
4 5
1 3
3 5

Output 1

1 2 5 3 4 6

Input 2

4
3 7
10 14
1 6
6 11

Output 2

1 3 2 4

Input 3

See ex_color3.in and ex_color3.ans in the provided files. This example satisfies the special constraints of Subtask 2.

Input 4

See ex_color4.in and ex_color4.ans in the provided files. This example satisfies the special constraints of Subtask 3.

Input 5

See ex_color5.in and ex_color5.ans in the provided files. This example satisfies the special constraints of Subtask 4.

Input 6

See ex_color6.in and ex_color6.ans in the provided files. This example satisfies the special constraints of Subtask 5.

Constraints

For all data, $0 \le N \le 2.5 \cdot 10^5$, $0 \le L_i < R_i \le 10^9$. For $1 \le i < j \le N$, it is guaranteed that $R_i - L_i \le R_j - L_j$, and it is not the case that $L_i = L_j$ and $R_i = R_j$ simultaneously.

• Subtask 1 (8 points): $N, R_i \le 100$.
• Subtask 2 (9 points): $N \le 10^4$.
• Subtask 3 (18 points): There do not exist $1 \le i, j \le N$ such that $L_i < L_j < R_j < R_i$.
• Subtask 4 (21 points): There do not exist $1 \le i, j \le N$ such that $L_i < L_j < R_i < R_j$.
• Subtask 5 (44 points): No special constraints.