Description

学过《操作系统》课程的同学都知道进程调度算法。如果你是学霸，那么你肯定能说出所有的调度算法，如果你是学渣，那么你是不是连进程调度算法是什么都忘啦。玩笑开完了，进入正题。。。
这是一个进程调度系统，采用的是优先度调度算法。可以这样理解，一个进程队列有n个进程（默认1<=pid<=n），每个进程有一个优先度Ai+Bi*t（t为时间）。随着时间的推进，然后CPU会在某个时刻Ti发出请求，要求取一个进程进入CPU，要求这个进程是在Ti时间剩余进程中优先度Ai+Bi*Ti最小的（如果优先度相等取pid更小的）。进程进入CPU后就不会再返回进程队列，进程队列的进程个数相应减少一个。因为有n个进程，CPU会发出n个Ti时刻的请求。
你能为这个调度算法编写一份代码吗，要求输出每个时刻Ti取的进程的pid。

Input

输入包括多组数据。第一行一个整数n（1<=n<=700000），代表进程个数。接着n行，pid依次为1到n，每行2个整数Ai,Bi（0<=Ai,Bi<=2^31-1)

Output

对于每组数据，输出一个序列，代表CPU依次取的进程pid，每个pid之间用空格隔开，没有多余的空格在最后。

Sample Input

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

Sample Output

1 4 2 5 3

HINT

Source

NBU OJ