Petya and Vasya are holding a programming competition. So many participants came to it,
that in order to register them all, Petya and Vasya had to work together.
In order to register, each participant calls his first name, last name and patronymic,
and Petya and Vasya enter this information into a common spreadsheet. Since there are many participants,
and there is so little time to organize, Petya and Vasya did not have time to agree on the data recording format
participant in the table and they had to improvise. Petya decided to write for each participant
first his last name, then his first name, and then — patronymic, and Vasya — first name, then patronymic, and
then — last name.
At the end of registration, it became clear that to sum up the results of the Olympiad, use
this table is impossible: it will be inconvenient for the participant to look for himself. It was decided to bring the table
to the following view:
x for all participants, the last name is written first, then the first name, and then — middle name;
x the participants in the table are ordered lexicographically by last name.
Petya and Vasya noticed that the surnames of all the participants are different, but each name occurs
at least twice. In this case, no name is neither a surname nor a patronymic of any of the
participants, similarly, no surname and patronymic are the same.
Use this information to help them shape the table they want.
Input data format
The first line contains the number n (2 ≤ n ≤ 1000) — the total number of records in the spreadsheet.
Next, n lines contain three words s1,i, s2,i, s3,i. Each of the words contains from 1 to 20 Latin
letters, the first letter is capitalized, and all other — lowercase. Each line matches
one of the entries made by Petya or Vasya. The words are separated by a single space.
Output Format
Print n lines — spreadsheet with each participant listed first
last name, then first name, then patronymic, and all entries are sorted lexicographically.
The lexicographical order corresponds to the order in dictionaries: words are compared first
by the first letter, then by the second, and so on. If the next letter in one of the words comes before the
alphabet, then this word is lexicographically smaller than the other. If the discrepancy is still not found,
that is, one of the words is a prefix of the other, then it is considered that the word that is the prefix is
lexicographically less.
Example
Input
4
Ivanov Ivan Ivanovich
Boris Ivanovich Petrov
Sergey Ivanovich Sidorov
Pavlov Sergey Borisovich
Conclusion
Ivanov Ivan Ivanovich
Pavlov Sergey Borisovich
Petrov Ivan Borisovich
Sidorov Sergey Ivanovich