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