Class Time

Interview

Time limit2sMemory limit256 MB

Summary

Sort the student names by last name, breaking ties by first name, and print them in that order.

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

Problem

It is the first day of class. Tom is teaching the class, and before anything else he takes attendance to see who showed up.

Tom calls the students in alphabetical order by last name. When two or more students share a last name, he calls those students in alphabetical order by first name.

Given the roster, print the order in which Tom calls the students.

Input

The first line contains an integer $n$ , the number of students in Tom's class. ( $1 \le n \le 100$ )

Each of the next $n$ lines contains the name of one student: the first name, a single space, then the last name. Both the first name and the last name start with an uppercase letter (A to Z) followed by one or more lowercase letters (a to z). Neither the first name nor the last name is longer than 10 letters.

No two students have exactly the same first name and last name, but students may share a first name, or share a last name.

Output

Print $n$ lines with the student names in the order Tom calls them. Write each line in the same format as the input: the first name, a single space, then the last name.

Examples2

Example 1

Input

3
John Adams
Bob Adam
Bob Adams

Expected output

Bob Adam
Bob Adams
John Adams

Example 2

Input

1
Coursera Educators

Expected output

Coursera Educators