Mr Anderson is teaching his class of avid computer science students, but he wants to make sure everyone is here. He plans to do a roll call, but the list of students he has been given is in random order!

"This is no good", he says, as he comes up with an idea. He will get his students to sort the list for him! When he was in school, Mr Anderson would always be at the top of the roll call, as his last name started with "A". He always felt a bit bad for the students who were always at the end of the roll call because of their last name.

To put an end to such injustices, he requests that students be sorted by their last name, and in reverse order. So students with last names starting with "Z" will be called out first, and students with last names starting with "A" will be called out last.

Input

The first line consists of an integer ~n\ (1 \leq n \leq 100)~ which represents the number of students in the class.

The next ~n~ lines consist of a string ~S\ (1 \leq S.\text{length} \leq 100)~ which represents the first and last name of the student. The string ~S~ only contains uppercase and lowercase English characters, with a space separating the first and last name. The first and last name will always start with an uppercase English character.

Output

Output the names of the students in reverse lexicographic order. Lexicographic order means that a comes before b, which comes before c, and so on. Uppercase letters come before lowercase letters.

Example

Input 1

6
Emma Johnson
Liam Davis
Olivia Brown
Noah Harris
Ava Clark
Elijah Martinez

Output 1

Elijah Martinez
Emma Johnson
Noah Harris
Liam Davis
Ava Clark
Olivia Brown

Because we want to sort names in reverse lexicographic order by their last name, we start with Elijah Martinez as "M" comes before "J" in Johnson, which comes before "H" in Harris, and so on.

Input 2

2
Anthony Johnson
Emma Johnson

Output 2

Emma Johnson
Anthony Johnson

If two students have the same surname, order it based on the reverse lexicographic order of their first name.

Input 3

4
James Wilson
Isabella Walker
Daniel Hill
Jacob Hiller

Output 3

James Wilson
Isabella Walker
Jacob Hiller
Daniel Hill

For James Wilson and Isabella Walker, both last names start with "W", so we look at the second letter. Since "i" comes after "a", we place Wilson before Walker as we are sorting in reverse lexicographic order. Hiller comes before Hill as it is longer.