19781번 - Регистрация на олимпиаду 다국어

Петя и Вася проводят олимпиаду по программированию. На нее пришло так много участников, что для того, чтобы их всех зарегистрировать, Пете Васе пришлось работать вдвоем.

Для того, чтобы зарегистрироваться, каждый участник называет свои имя, фамилию и отчество, а Петя и Вася заносят эту информацию в общую электронную таблицу. Так как участников много, а времени на организацию так мало, Петя и Вася не успели договориться о формате записи данных участника в таблицу и им пришлось импровизировать. Петя решил писать для каждого участника сначала его фамилию, затем имя, а затем --- отчество, а Вася --- сначала имя, затем отчество, а затем --- фамилию.

По окончании регистрации, стало понятно, что для подведения итогов олимпиады использовать данную таблицу невозможно: участнику будет неудобно себя искать. Было решено привести таблицу к следующему виду:

• для всех участников сначала написана фамилия, затем имя, а затем --- отчество;
• участники в таблице упорядочены лексикографически по фамилии.

Лексикографический порядок соответствует порядку в словарях: слова сначала сравниваются по первой букве, затем по второй и т.д. Если очередная буква в одном из слов меньше, то это слово лексикографически меньше другого. Если же расхождение так и не найдено, то есть одно из слов является префиксом другого, то считается, что оно меньше.

Петя и Вася заметили, что фамилии у всех участников различны, а вот каждое имя встречается хотя бы два раза. При этом никакое имя не является ни фамилией, ни отчеством никакого из участников, аналогично никакие фамилия и отчество не совпадают.

Пользуясь этой информацией, помогите им привести таблицу к желаемому виду.

В первой строке задано число $n$ ($2 \le n \le 1000$) --- общее число записей в электронной таблице. Далее, в $n$ строках записано по три слова $s_{1,i}$, $s_{2,i}$, $s_{3,i}$. Каждое из слов содержит от 1 до 20 латинских букв, первая буква является заглавной, а все остальные --- строчными. Каждая строка соответствует одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.

Выведите $n$ строк --- электронную таблицу, в которой для каждого участника идет сначала фамилия, потом имя, потом отчество, причем все записи отсортированы лексикографически.