Sort Students by Two CriteriaMedium

Sort Students by Two Criteria

MediumPractice library · +20 XPsortingstable sort

You are given a list of students, each with a programming score and a math score. You need to sort them according to two criteria: first, by programming score in descending order, and second, for students with the same programming score, by math score in ascending order. Print the students in the sorted order.

Input

The first line contains an integer N, the number of students. Each of the following N lines contains two space-separated integers: the programming score and the math score for a student.

Output

Print N lines, each containing two space-separated integers, representing the programming score and math score of students in the sorted order.

Constraints

1 <= N <= 200000. 0 <= programming score, math score <= 1000000.

Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests

Example 1

Input
5
80 90
70 100
80 85
90 70
70 95
Output
90 70
80 85
80 90
70 95
70 100

Students sorted by programming score descending, then math score ascending.

Example 2

Input
3
100 50
100 60
90 70
Output
100 50
100 60
90 70

Students with the same programming score are sorted by math score.

Hints