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

Суффиксы одной строки

Суффиксы одной строки

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Вам задан набор s_1, s_2, ..., s_n, состоящий из n строк.

Требуется определить существует ли такая строка t, что любая из заданных строк является некоторым ее суффиксом.

Входные данные

В первой строке записано целое число n (1n10^5) — количество строк в наборе. В каждой из следующих n строк записана строка. В i-той из них записана непустая строка s_i.

Все строки состоят только из строчных латинских символов. Суммарная длина заданных строк не превосходит 10^5.

Выходные данные

Если строка t существует, выведите ее. Если существует несколько строк t, выведите строку с минимальной длиной.

Выведите -1, если строки t, описанной в условии, не существует.

Пример

Входные данные #1
3
aaa
aa
a
Выходные данные #1
aaa
Автор Геральд Агапов
Источник Летняя школа Севастополь 2013, Волна 1, День 6