eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Конкатенація

Конкатенація

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Розглянемо два рядки α та β. Їх конкатенацією називається рядок, який отримується в результаті дописування до рядка α рядка β. Цей рядок позначається αβ. Наприклад, конкатенацією рядків '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').

Приклад

Вхідні дані #1
a
aabb
ab
ac
b
bac
Вихідні дані #1
a
ac
b