Задачі
Суфікси одного рядка
Суфікси одного рядка
Вам задано набір s\[1\], s\[2\], ..., s\[n\], який складається з n
рядків.
Потрібно визначити чи існує такий рядок t
, що довільний із заданих рядків є деяким його суфіксом.
Вхідні дані
У першому рядку записано ціле число n
(1 ≤ n ≤ 10^5
) — кількість рядків у наборі. У кожному з наступних n
рядків записано рядок. У i
-тому з них записано непорожній рядок s\[i\].
Усі рядки складаються лише з рядкових латинських символів. Сумарна довжина заданих рядків не перевищує 10^5
.
Вихідні дані
Якщо рядок t
існує, виведіть його. Якщо існує декілька рядків t
, виведіть рядок з мінімальною довжиною.
Виведіть -1
, якщо рядка t
, описаного в умові, не існує.
Приклад
Вхідні дані #1
3 aaa aa a
Вихідні дані #1
aaa