Kat Mandu has been living in seclusion for several years, practicing martial arts and meditating. As a consequence, he missed the take-off of social networking. He was therefore surprised upon his return to society that countless many are standing with signs at every street corner, eager to be followed on Twitter; his grandmother runs one of the world's top blogs; and chances are, even your mom has Facebook.

Reluctantly, he joined the craze, but he quickly discovered that many of these services are lacking in their friend sorting facilities: they will usually only allow listing friends in alphabetical order by name. Kat Mandu would prefer sorting his friends by age, with the oldest at the top of the list. If two friends have the same age, only then sort alphabetically. Help Kat Mandu by writing a program which implements this functionality.

Input

Each line of input will contain a name and an age, separated by a space. Names will be unique and consist of at most 10 uppercase letters. Ages will be between 1 and 100 inclusive.

Output

Print out the same names that were given in the input, but sorted according to Kat Mandu's requirements.

Example

Input:
DUCHESS 26
MARIE 8
BERLIOZ 8
TOULOUSE 7
THOMAS 28

Output:
THOMAS
DUCHESS
BERLIOZ
MARIE
TOULOUSE