F. Books
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ryan is a bookworm. He has many books on his shelf, and he wants to sort them alphabetically by their first letter. Furthermore, he wants to sort the books that have the same starting letter by their published years, from oldest to most recent. Note that all the book titles are one word, with all lowercase letters.

Input

The first line has an integer $$$1 \lt N \lt 10000$$$, representing the number of books Ryan has on his shelf.

The next $$$N$$$ lines contain $$$A$$$ and $$$B$$$, where $$$A$$$ is the name of the book (the length of the book title will be $$$3 \leq A \lt 13$$$) and $$$0 \leq B \lt 10000$$$ is the publish year.

Output

Print the final sorted bookshelf, with the name of each book on a separate line.

Example
Input
4
harry 1987
orange 1776
hotels 1973
moon 2018
Output
hotels
harry
moon
orange
Note

Problem idea: Spark

Problem preparation: Spark

Occurances: Novice 6