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

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

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

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

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

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

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

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