Безопасный пароль

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

Мсье Бук подсказал ему, что безопасным называется пароль, который не содержит трех или более одинаковых символов подряд, а также никакой символ которого не встречается в ней чаще, чем в половине позиций.

Помогите Пуаро получить из придуманной им строки безопасный пароль при помощи минимального количества операций вида <<заменить $i$-й символ строки на $c$>>.

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

Выведите в единственной строке полученный безопасный пароль.