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 () representing the unique identifier of a team and the score the team earned.

Output

The program should print n lines. Each line should contain two integers - the id of the team, and their score.