Sort & Search

Testing System

Junior Programmer Sasha wrote his first testing system. He was so happy to compile it, that he decided to invite school friends at his own contest.

But at the end of the contest it became clear that the system can't sort the teams in the results table. Help Sasha to implement this sort.

The teams are ordered according to ACM rules:

  • by the number of solved tasks in descending order;
  • if the number of solved problems equal - sort by the time penalty in ascending order;
  • if all mentioned parameters are equal - sort by the team number in ascending order.


The first line contains the number of teams n (1n100000) that takes part in the contest. The i-th of the next n lines contains the number of solved problems s (0s100) and the penalty time t (0t100000) for the team with number i.


Print n numbers - the team numbers in the sorted order.

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
3 50
5 720
1 7
0 0
8 500
Output example #1
5 2 1 3 4
Source 2012 ЛКШ August Parallel B1 Day 1, Problem B