Будем называть разнообразностью строки количество символов,
которые встречаются в ней равно один раз. Например, разнообразность строки
"INFORMATICS" — 9,
поскольку символы "A",
"C", "F", "M", "N", "O", "R", "S" и "T" встречаются в ней ровно
один раз.
Для заданной строки S найдите
подстроку, которая имеет наибольшую разнообразность. Если таких подстрок
несколько, то найдите ту, которая минимальна в лексикографическом порядке.
Строка A меньше строки B в лексикографическом порядке, если выполняется одно из
условий:
1) A является началом B;
2) для некоторого числа i
первые i символов строки A
совпадают с первыми i символами строки B, а i + 1-й символ в
строке A идёт в алфавите раньше i + 1-го символа в строке B.
Например, строка "SOL"
меньше в лексикографическом порядке строк "SOLVE", "START", "TIME".
Формат входных данных
Входной файл содержит строку, состоящую только из заглавных
букв латинского алфавита. Длина строки не превышает 2500 символов.
Формат выходных данных
Выведите в выходной файл подстроку исходной строки, имеющую
максимальную разнообразность среди всех её подстрок. Если таких подстрок
несколько, выведите минимальную в лексикографическом порядке.
Примеры входных и выходных файлов
|
stdin
|
stdout
|
|
ABBAC
|
BAC
|
|
OLYMP
|
OLYMP
|
|
AAA
|
A
|
|
AABBCC
|
AB
|
