Доктор Мориарти посылает сообщение Шерлоку Холмсу. В его распоряжении имеется строка s.

Строка p называется подстрокой строки s, если ее можно прочитать, начиная с некоторой позиции в строке s. Например, у строки «aba» есть шесть подстрок: «a», «b», «a», «ab», «ba», «aba».

Доктор Мориарти планирует вырезать из строки s некоторую подстроку, назовем ее t. Потом он должен ноль или более раз изменить вырезанную подстроку t. В результате должна получиться фиксированная строка u (именно ее нужно отправить Шерлоку Холмсу). За одно изменение считается одно из следующих действий:

• Вставить одну букву с любого конца строки.
• Удалить одну букву с любого конца строки.
• Заменить одну любую букву на любую другую.

Мориарти очень умен, поэтому после выбора какой-то подстроки t он всегда делает минимальное количество изменений, чтобы получить u.

Помогите Мориарти выбрать среди всех подстрок строки s наилучшую подстроку t такую, что количество сделанных им изменений для получения из нее строки u будет минимально.