H. Регистрация на олимпиаду

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

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

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

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

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

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

Формат входного файла

В первой строке задано число n (2 ≤ n ≤ 1000) – общее число записей в электронной таблице. Далее, в n строках записано по три слова s_1,i, s_2,i, s_3,i. Каждое из слов содержит от 1 до 20 латинских букв, первая буква является заглавной, а все остальные – строчными. Каждая строка соответствует одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.

Формат выходного файла

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

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

Пример:

Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение



Версия для печати