Class Time

It's the first day of class! Tom is teaching class and first has to take attendance to see who is in class. He needs to call the students' names in alphabetical order by last name. If two students have the same last name, then he calls the students with that same last name in alphabetical order by first name. Help him!

Input

The first line contains an integer $n(1\le n\le 100)$, the number of students in Tom's class. Each of the following $n$ lines contains the name of a single student: first name, followed by a single space, then last name. The first and last name both start with an uppercase letter $(A-Z)$ and then be followed by one or more lowercase letters $(a-z)$. The first and last name of each student is no more than $10$ letters long each.

It is guaranteed that no two students have exactly the same name, though students may share the same first name, or the same last name.

Output

Output $n$ lines, the names of the students as Tom calls them in the desired order.

Examples