Korean, English, math

Interview

Time limit1sMemory limit256 MB

Summary

Sort N students by Korean score descending, English ascending, math descending, then name in ASCII order and print the names.

Level: Easy3 of 10
Topics: Sorting
Solved: No attempts yet

Problem

You are given the name and the Korean, English, and math scores of N students. Write a program that sorts the students by the following rules, applied in order.

Korean score in decreasing order
If the Korean scores are equal, English score in increasing order
If the Korean and English scores are equal, math score in decreasing order
If all three scores are equal, name in increasing dictionary order

Names are compared by ASCII value. An uppercase letter has a smaller value than a lowercase letter, so it comes first.

Input

The first line contains the number of students N ( $1 \le N \le 100000$ ).

Each of the next N lines contains a student's name and Korean, English, and math scores, separated by single spaces. Every score is a natural number between 1 and 100. A name consists only of uppercase and lowercase letters and is at most 10 characters long. Two or more students may share the same name.

Output

Print the name of each student on its own line, N lines in total, in the sorted order.

Examples6

Example 1

Input

12
Junkyu 50 60 100
Sangkeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Haebin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90
Sanghyun 70 70 80
nsj 80 80 80
Taewhan 50 60 90

Expected output

Donghyuk
Sangkeun
Sunyoung
nsj
Wonseob
Sanghyun
Sei
Kangsoo
Haebin
Junkyu
Soong
Taewhan

Example 2
Input
```
1
Solo 1 1 1
```
Expected output
```
Solo
```

Example 3

Input

6
abc 50 50 50
ABC 50 50 50
Abc 50 50 50
aBC 50 50 50
z 50 50 50
Z 50 50 50

Expected output

ABC
Abc
Z
aBC
abc
z

Example 4

Input

5
Alice 90 10 50
Bob 90 100 50
Carol 90 55 50
Dave 100 1 1
Eve 1 100 100

Expected output

Dave
Alice
Carol
Bob
Eve

Example 5

Input

4
One 70 70 1
Two 70 70 100
Three 70 70 50
Four 70 70 99

Expected output

Two
Four
Three
One

Example 6

Input

6
lo 1 1 1
hi 100 100 100
mix 100 1 100
mid 50 50 50
edge 1 100 1
zz 100 1 1

Expected output

mix
zz
hi
mid
lo
edge