Есть следующая задача: Хорошо известно, что анекдоты меняются из уст в уста и проследить за всеми изменениями довольно сложно.

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

«push_x» – добавить букву «x» в конец слова; «pop» – удалить последнюю букву (этот тип применим только для непустых слов). Анекдотолог Иван собрал историю одного анекдота – все версии анекдота, полученные корректной последовательностью изменений начиная с пустого слова, но есть нюанс. К сожалению, версии даны в произвольном порядке, а для публикации в научном журнале нужно восстановить последовательность изменений.

Помогите Ивану – найдите последовательность изменений такую, что применив её к изначально пустому слову, набор всех промежуточных версий совпадёт с имеющейся историей не учитывая порядка.

Входные данные Первая строка входного файла INPUT.TXT содержит целое число n – количество версий (1 ≤ n ≤ 3 000).

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

Суммарная длина слов не превосходит 10^6.

Гарантируется, что слова получены корректной последовательностью изменений, описанных в условии задачи, начиная с пустого слова.

Выходные данные В выходной файл OUTPUT.TXT выведите список из n−1 изменений в том порядке, в котором их нужно выполнять. Каждое изменение должно быть описано в отдельной строке.

Список слов, полученных этим списком действий, должен совпадать с данным списком слов, не учитывая порядка.

Пример входного теста: 6 "" "" "a" "b" "ab" "a"

Пример выходного: push_b pop push_a push_b pop

Сначала строим Бор по входных данным, причем со счётчиком (учитывает сколько раз каждое слово встречается во входном multiset). Далее нужно как-то обойти дерево, причем обход необязательно от корня до корня, он может заканчиваться в любой вершине, так чтобы после выполнения действий в выходном файле получался такой же multiset как и во входном. Какие идеи решения?