在一个寒冷的冬夜,我们的英雄 Vasya 站在铁路队列中购买 Codeforces 冠军决赛的门票。与往常一样,收银员说他要离开 5 分钟,然后就离开了一个小时。然后Vasya为了不觉得无聊,开始分析队列这样的机制。这一发现让瓦夏大吃一惊。
每个人都有两个数字来表征:ai,这是他当前任务的重要性(数字越大,任务越重要)和数字ci,这是他良心的写照。数字 ai 形成从 1 到 n 的数字排列。
设队列目前由 n - 1 个人组成。让我们看看第 n 号来的人的行为方式。首先,他站在队列的末尾,并执行以下操作:如果他前面的人的任务 ai 的重要性小于 an,则他们交换位置(看起来像这样:编号为 n 的人问他前面的人:“呃……请原谅,但这对我来说非常重要……你能让我在队列中移动吗?”),然后他再次向他前面的人提出问题,依此类推。但如果 ai 大于 an,则队列停止向上移动。然而,编号为n的人最多可以执行cn次操作。
在我们的任务中,我们假设当 n 号加入队列时,n - 1 之间的交换过程将停止。如果交换是可能的,那么它必然会发生。
你的任务是帮助 Vasya 对所描述的过程进行建模,并找到当所有交换停止时人们排队的顺序。
输入
第一个输入行包含一个整数 n,它是加入队列的人数 (1 ≤ n ≤ 105)。在接下来的 n 行中,按照人们到来的顺序给出了对人的描述 - 空格分隔的整数 ai 和 ci (1 ≤ ai ≤ n, 0 ≤ ci ≤ n)。每个描述都位于单行中。所有的ai都是不同的。
输出
输出从1到n的数字排列,表示按照上述规则从头到尾形成的队列。在这个序列中,第 i 个数字代表交换结束后将在第 i 个位置排队的人的号码。人员按照输入中给出的顺序从 1 开始编号。用空格分隔数字。
示例
输入 #1
2 1 0 2 1
输出 #1
2 1
输入 #2
3 1 3 2 3 3 3
输出 #2
3 2 1
输入 #3
5 2 3 1 4 4 3 3 1 5 2
输出 #3
3 1 5 4 2