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

Суфікси одного рядка

Суфікси одного рядка

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

Вам задано набір 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
Автор Геральд Агапов
Джерело Літня школа Севастополь 2013, Хвиля 1, День 6