给定数轴上的 $N$ 个区间 $[L_i,R_i)$，满足两两不同且长度单调不降，即对 $1\le i<j\le n$ 保证 $R_i-L_i\le R_j-L_j$，且 $L_i=L_j$ 和 $R_i=R_j$ 不同时成立。

初始时数轴是白色的，进行 $N$ 次操作，每次选择一个之前没有选择过的区间 $[L_i,R_i)$，将这个区间染成黑色，要求染完之后黑色部分的总长度尽量小，若相同则选择编号最小的。求每次操作选择的区间的编号。

输入格式

第一行，一个正整数 $N$。

之后 $N$ 行，每行两个非负整数 $L_i,R_i$。

输出格式

一行，$N$ 个正整数，第 $i$ 个正整数表示第 $i$ 次选择的区间的编号。

样例一

input

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

output

1 2 5 3 4 6

样例二

input

4
3 7
10 14
1 6
6 11

output

1 3 2 4

样例三

见下发文件中的 ex_color3.in 和 ex_color3.ans，该样例符合子任务 $2$ 的特殊限制。

样例四

见下发文件中的 ex_color4.in 和 ex_color4.ans，该样例符合子任务 $3$ 的特殊限制。

样例五

见下发文件中的 ex_color5.in 和 ex_color5.ans，该样例符合子任务 $4$ 的特殊限制。

样例六

见下发文件中的 ex_color6.in 和 ex_color6.ans，该样例符合子任务 $5$ 的特殊限制。

数据范围

对于所有数据，$0 \le N\le 2.5\cdot 10^5$，$0\le L_i<R_i\le 10^9$，对 $1\le i<j\le n$ 保证 $R_i-L_i\le R_j-L_j$，且 $L_i=L_j$ 和 $R_i=R_j$ 不同时成立。

• 子任务 $1$（$8$ 分）：$N,R_i\le 100$；
• 子任务 $2$（$9$ 分）：$N\le 10^4$；
• 子任务 $3$（$18$ 分）：不存在 $1\le i,j\le n$ 使得 $L_i<L_j<R_j<R_i$；
• 子任务 $4$（$21$ 分）：不存在 $1\le i,j\le n$ 使得 $L_i<L_j<R_i<R_j$；
• 子任务 $5$（$44$ 分）：无特殊限制。

时间限制：$\texttt{5s}$

空间限制：$\texttt{512MB}$