Speed up the ranking algorithm
At an old tournament, the software engineers implemented a ranking algorithm based on bubble sort. Back then the tournament didn’t have many participants - so that worked okay. But now the number of participants is too many. They ask you to speed up the ranking algorithm.
Each team has a unique number (an identifier) and a score. The teams have to be ordered in descending order of scores (highest scores first, lowest scores last), and the teams with the same scores should stay relevant to the order they appear in the input. So, you should implement a stable sort.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next
n lines contain space-separated pairs Output
The program should print
n lines. Each line should contain two integers - the id of the team, and their score.Examples
Input | Output |
6
1 10
4 20
5 7
2 20
8 10
9 15 | 4 20
2 20
9 15
1 10
8 10
5 7 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 10 MB