Автодополнение — функция в программах, предусматривающих ввод текста (редакторы, оболочки командной строки, браузеры и т. д.), по дополнению текста по введенной его части. Вася занимается разработкой нового браузера BERowser. Сейчас он как раз работает над функцией автодополнения в адресной строке. Известен список из n последних посещенных пользователем страниц, а так же введенная часть s. Ваша задача — дополнить s до адреса одной из страниц из списка. Вы должны найти лексикографически наименьший адрес, имеющий префикс s.
Выходные данные
Если s не является началом какого-либо из n адресов посещенных страниц, выведите s. Иначе выведите лексикографически наименьший адрес одной из посещенных страниц, который начинается на s.
Лексикографический порядок — это порядок слов в словаре. Лексикографическое сравнение строк реализует оператор '<' в современных языках программирования.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
next
2
nextpermutation
nextelement
|
nextelement
|
|
2
|
find
4
find
findfirstof
findit
fand
|
find
|
|
3
|
find
4
fondfind
fondfirstof
fondit
fand
|
find
|