История одного анекдота
(Время: 1 сек. Память: 256 Мб Сложность: 74%)
Хорошо известно, что анекдоты меняются из уст в уста и проследить за всеми изменениями довольно сложно.
Пользуясь методами современной анекдотологии, любой анекдот можно представить в виде слова, состоящего из строчных букв латинского алфавита, а изменение анекдота может быть одного из двух типов:
- «push_x» – добавить букву «x» в конец слова;
- «pop» – удалить последнюю букву (этот тип применим только для непустых слов).
Анекдотолог Иван собрал историю одного анекдота – все версии анекдота, полученные корректной последовательностью изменений начиная с пустого слова, но есть нюанс. К сожалению, версии даны в произвольном порядке, а для публикации в научном журнале нужно восстановить последовательность изменений.
Помогите Ивану – найдите последовательность изменений такую, что применив её к изначально пустому слову, набор всех промежуточных версий совпадёт с имеющейся историей не учитывая порядка.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n – количество версий (1 ≤ n ≤ 3 000).
В следующих n строках содержится по одному слову, состоящему из строчных букв латинского алфавита и записанному в кавычках.
Суммарная длина слов не превосходит 106.
Гарантируется, что слова получены корректной последовательностью изменений, описанных в условии задачи, начиная с пустого слова.
Выходные данные
В выходной файл OUTPUT.TXT выведите список из n−1 изменений в том порядке, в котором их нужно выполнять. Каждое изменение должно быть описано в отдельной строке.
Список слов, полученных этим списком действий, должен совпадать с данным списком слов, не учитывая порядка.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5
"a"
"b"
""
""
"" | push_a
pop
push_b
pop |
2 | 6
""
""
"a"
"b"
"ab"
"a" | push_b
pop
push_a
push_b
pop |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|