题目描述

技术是你最喜欢的一门科目了，它上可以敲代码，中可以做电工，下可以敲小板凳。技术老师是一个小老头，他时常怀念自己在大学的 KFC 餐厅当老板的日子，据他所说，每到星期四，就会有诸多大学生前往 KFC 消费，他把这一现象称之为 Chinese Collegiate Purchasing Crazythursday ，简称 CCPC 现象。技术老师清晰的记得店里每周的星期四都会出现 CCPC 现象，但有一周的星期四似乎比往常更加热闹。

现在，有 $N$ 名大学生同时来到了老师的店里，他们中的每个人都想尽快取餐，越落后他们越不满意，很不幸的是，店里对此没有任何准备，他们每个人的套餐你都必须现场制作。

具体地，对于第 $i$ 名大学生来说，他的套餐需要 $t_i$ 单位时间制作完成，他每在店中等待 $1$ 个单位的时间,便会产生 $h_i$ 点不满度。店里的后厨在同一时间只能制作一份套餐。

为了创造一个良好的就餐环境，请你针对这些大学生设计一个出餐顺序，使得最后所有人的不满度之和最小。

输入格式

第一行输入一个正整数 $N$ $(1 \leq N \leq 2 \cdot 10^5 )$ ，代表店内的大学生总数。

接下来的 $N$ 行中，第 $i$ 行 输入两个被空格隔开的正整数 $t_i \enspace h_i$ $( 1 \le t_i,h_i \le 10^9 )$，代表编号为 $i$ 的大学生的套餐制作用时与其每个时间单位的等待产生的不满度。

输出格式

输出一行 $N$ 个被空格隔开的正整数，代表使店内所有大学生最终产生的不满度总和最小的出餐顺序。

如果存在多个合法的答案，输出$\textbf{使编号较小的大学生取餐顺序尽量靠前}$的那个。

样例

3
3 4
1 2
5 6

2 1 3 

3
1 1
1 1
1 1

1 2 3

4
2 5
1 3
3 5
1 3

2 4 1 3

样例解释

对于样例一，能产生的最小不满度之和为 $2+16+54=72$ 。可以证明没有其他顺序能使最终不满度之和小于等于 $72$ 。

对于样例二，不管如何排列，最终的不满度总和都相等，即所有排列方式都是合法答案，此时，我们输出使编号较小者更靠前的那一个答案，即 $1 \enspace 2 \enspace 3$。