Петя и Вася проводят олимпиаду по программированию. На нее пришло так много участников,
что для того, чтобы их всех зарегистрировать, Пете и Васе пришлось работать вдвоем.
Для того, чтобы зарегистрироваться, каждый участник называет свои имя, фамилию и отчество,
а Петя и Вася заносят эту информацию в общую электронную таблицу. Так как участников много,
а времени на организацию так мало, Петя и Вася не успели договориться о формате записи данных
участника в таблицу и им пришлось импровизировать. Петя решил писать для каждого участника
сначала его фамилию, затем имя, а затем — отчество, а Вася — сначала имя, затем отчество, а
затем — фамилию.
По окончании регистрации стало понятно, что для подведения итогов олимпиады использовать
данную таблицу невозможно: участнику будет неудобно себя искать. Было решено привести таблицу
к следующему виду:
• для всех участников сначала написана фамилия, затем имя, а затем — отчество;
• участники в таблице упорядочены лексикографически по фамилии.
Петя и Вася заметили, что фамилии у всех участников различны, а вот каждое имя встречается
хотя бы два раза. При этом никакое имя не является ни фамилией, ни отчеством никакого из
участников, аналогично никакие фамилия и отчество не совпадают.
Пользуясь этой информацией, помогите им привести таблицу к желаемому виду.
Формат входных данных
В первой строке задано число n (2 ≤ n ≤ 1000) — общее число записей в электронной таблице.
Далее, в n строках записано по три слова s1,i, s2,i, s3,i. Каждое из слов содержит от 1 до 20 латинских
букв, первая буква является заглавной, а все остальные — строчными. Каждая строка соответствует
одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.
Формат выходных данных
Выведите n строк — электронную таблицу, в которой для каждого участника идет сначала
фамилия, потом имя, потом отчество, причем все записи отсортированы лексикографически.
Лексикографический порядок соответствует порядку в словарях: слова сначала сравниваются
по первой букве, затем по второй и т.д. Если очередная буква в одном из слов идет раньше в
алфавите, то это слово лексикографически меньше другого. Если же расхождение так и не найдено,
то есть одно из слов является префиксом другого, то считается, что слово, являющееся префиксом,
лексикографически меньше.
Пример
Ввод
4
Ivanov Ivan Ivanovich
Ivan Borisovich Petrov
Sergey Ivanovich Sidorov
Pavlov Sergey Borisovich
Вывод
Ivanov Ivan Ivanovich
Pavlov Sergey Borisovich
Petrov Ivan Borisovich
Sidorov Sergey Ivanovich