Рабочее место участника

Рассмотрим две строки `α` и `β`. Их конкатенацией называется строка, получающаяся в результате приписывания к строке `α` строки `β`. Эта строка обозначается `αβ`. Например, конкатенацией строк 'ab' и 'ac' будет строка 'abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.

Рассмотрим некоторое множество `W`, состоящее из строк. Назовём его замыканием множество `W^{*}`, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества `W`. Таким образом, множество `W^{*}` содержит пустую строку, и если строка `α` принадлежит множеству `W^{*}`, а строка `β` принадлежит множеству `W`, то строка `αβ` принадлежит множеству `W^{*}`. Более того, все элементы множества `W^{*}` можно представить в таком виде, то есть `W^{*}` является пересечением всех множеств с указанными выше свойствами. Например, если `W`={a,ab}, то `W^{*}` состоит из всех строк, в которых перед каждой буквой 'b' идёт хотя бы одна буква 'a'.

Задано некоторое множество строк `W`. Требуется найти множество `X`, такое, что `W^{*}=X^{*}` и множество `X` имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если `W`={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.

Ввод состоит из набора строк, каждая из которых является элементом множества `W`. Каждая строка из множества `W` встречается во входном файле хотя бы один раз. Суммарная длина всех строк во входном файле не превосходит `10^4`. Количество строк во входном файле не превосходит `10^4`. После каждой строки из множества `W` во входном файле идёт перевод строки (пара символов с ASCII кодами 13 и 10). Строки состоят из символов с ASCII кодами от 33 до 126 включительно.

Выведите элементы одного из множеств `X`, удовлетворяющих условиям задачи. Каждая строка множества `X` должна быть выведена ровно один раз. Строки должны идти в лексикографическом порядке (лексикографический порядок используется в словарях, в этом порядке строка 'ab' меньше строки 'aba' и строка 'ab' меньше строки 'ac'). После каждой строки множества `X` должен идти один перевод строки.

a
aabb
ab

ac
b
bac

a
ac
b