Безопасный пароль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

Пример

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