E. Али идет за покупками
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Али Кучулу собирается пойти за подарками к Наврузу, древнему персидскому празднику, иранскому новому году.

Когда Али вошел в магазин, он сразу понял, что когда-то хозяин магазина тоже был программистом. Но программистом много денег не заработаешь, и ему пришлось сменить работу. Хозяин сказал Али, что тот может взять бесплатно что угодно, если ответит на простой вопрос за 10 секунд. Правда, чтобы увидеть вопрос, нужно было заплатить 3 томана.

Али сразу же согласился, и хозяин магазина дал ему листок бумаги, на котором было задание. Оно было очень простым:

Пусть строка Aababababababab. Какая непустая подстрока A встречается в ней чаще всего?

Али тут же ответил: a. Но хозяин сказал, что это неправильно, и попросил его дочитать условие до конца:

Если есть несколько таких подстрок, выберите самую длинную из них. Если их все равно несколько, выберите ту из них, что идет позже других в алфавитном порядке.

Правильный ответ был ab.

Сейчас Али просит вас решить эту задачу для других строк. А у вас есть для этого компьютер и странный язык.

Входные данные

В первой строке входных данных записана строка A. Эта строка непуста, состоит из маленьких латинских букв и содержит не более 30 символов.

Выходные данные

В первую строку выведите ответ.

Примеры
Входные данные
abab
Выходные данные
ab
Входные данные
abcd
Выходные данные
abcd