Olympiad Registration

Petya and Vasya are running a programming olympiad. So many participants showed up that Petya and Vasya had to work together to register all of them.

To register, each participant states their first name, last name, and patronymic, and Petya and Vasya enter this information into a shared spreadsheet. Because there are many participants and so little time to organize, Petya and Vasya did not agree on a format for writing a participant's data into the table and had to improvise. Petya decided to write each participant's last name first, then first name, then patronymic, while Vasya wrote first name first, then patronymic, then last name.

After registration ended, it became clear that this table could not be used to summarize the olympiad results: it would be inconvenient for a participant to find themselves. They decided to bring the table to the following form:

• for every participant, the last name is written first, then the first name, then the patronymic;
• the participants in the table are ordered lexicographically by last name.

Lexicographic order matches the order in dictionaries: words are compared by the first letter, then by the second, and so on. If the current letter in one word is smaller, that word is lexicographically smaller than the other. If no difference is found, that is, one of the words is a prefix of the other, then it is considered smaller.

Petya and Vasya noticed that all participants have distinct last names, while every first name occurs at least twice. No first name is a last name or patronymic of any participant, and likewise no last name and patronymic coincide.

Using this information, help them bring the table to the desired form.

The first line contains the number $n$ ($2 \le n \le 1000$), the total number of records in the spreadsheet. Then $n$ lines each contain three words $s_{1,i}$, $s_{2,i}$, $s_{3,i}$. Each word contains from 1 to 20 Latin letters, the first letter is uppercase and all the rest are lowercase. Each line corresponds to one of the records made by Petya or Vasya. The words are separated by a single space.

Output $n$ lines: the spreadsheet in which each participant has the last name first, then the first name, then the patronymic, with all records sorted lexicographically.