Будем называть разнообразностью строки количество символов, которые встречаются в ней равно один раз. Например, разнообразность строки "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