Задача D. Юбилейная задача

Автор:Д. Попов, М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Пете и Васе было поручено придумать задачу к 20-му четвертьфиналу ACM ICPC в их городе.

Петя долго думал и придумал следующую задачу: дана строка S, найти наиболее часто встречающуюся подстроку в ней.

Вася сказал, что такая задача не подойдет, она слишком простая. Тогда Петя предложил искать наиболее часто встречающуюся подстроку, и, если таких несколько, ответом будет, максимальная по длине. А если и таких несколько — лексикографически наименьшая среди таких.

Напишите программу, решающую предложенную Петей задачу.

Формат входного файла

Входной файл содержит единственную строку S, состоящую из строчных латинских букв.

Формат выходного файла

Выходной файл должен содержать лексикографически наименьшую из самых длинных из самых часто встречающихся подстрок строки S.

Ограничения

1 ≤ |S| ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
aaaa
a
2
ababab
ab
3
zxcvasqzx
zx

0.094s 0.012s 13