现在有 $10^9$ 个花盆，依次编号为 $1,2,\dots,10^{9}$ 。

给定 $n$ 个二元组 $L_i,R_i(L_i<R_i)$ ，我们将进行 $n$ 次以下操作：

1. 设当前第 $i$ 个二元组的权值是满足花盆 $x$ 为空且 $L_i<x\le R_i$ 的 $x$ 数量。选出未被选过且权值最小的二元组 $p$ 。如果存在多个权值最小的二元组，选择其中编号最小的。

2. 对于 $L_p<x\le R_p$ ，在花盆 $x$ 中种上花。

请求出每次操作选择出的二元组 $p$。

保证对于 $1\le i<j\le n,R_i-L_i\le R_j-L_j$ 。

输入格式

第一行包含一个整数 $n$ ，表示二元组的个数。

接下来 $n$ 行，每行包含两个整数 $L_i,R_i$ 。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 次操作中选择的二元组。

样例

样例输入

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

样例输出

1 2 5 3 4 6

数据范围

对于所有数据，$1\le n\le 2.5*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$ 。

子任务 1 ( 20% ) ： $n\le 5*10^3$ 。

子任务 2 ( 20% ) ： $L_i=0$ 或 $R_i=10^{9}$ 。

子任务 3 ( 30% ) ： $n\le 4*10^{4}$ 。

子任务 4 ( 30% ) ： 无特殊限制。