#311. 赛码学院的志愿者

赛码学院的志愿者

题目描述

赛码学院总共召集了 n位志愿者来负责打扫活动,现在需要你负责帮忙统计每位志愿者的工作情况,用来制作光荣榜,给他们发小花花。

第 i 位志愿者有一个工作时长 t_i ,以及他负责的工作的难度系数 k_i,一名志愿者的贡献度可以用 k_i *t_i确定。

现在要为这些志愿者的贡献度从大到小排个序,请你完成这个任务。相同贡献度的志愿者以工作时长较长的排在前面。如果贡献和时长一样,那么编号小的志愿者排在前面。

输入格式

一行一个整数 n ,表示志愿者的数量。

接下来 n 行,每行两个使用空格隔开的整数 t_i,k_i,表示第 i 名志愿者的时间和难度系数。

输出格式

一行,共n 个整数,第 i 个数表示排名为 i 的志愿者的序号,从 1 开始编号。

请注意本题时限为 5s,输入输出规模较大,请注意常数因素对耗时的影响。

样例

输入样例

3
1 2
2 3
3 4

输出样例

3 2 1

数据范围与提示

对于 40% 的数据,满足 1≤n≤100; 对于额外 20% 的数据,满足 k_i=1; 对于 100% 的数据,满足 1 <n <100000