Безопасный пароль
시간 제한2초메모리 제한1024 MB
길이가 25 이하인 문자열에서 같은 글자가 세 번 연속으로 나오지 않고 어떤 글자도 전체 위치의 절반을 넘지 않도록 최소 횟수의 문자를 바꾼다.
문제
Однажды Эркюль Пуаро решил изменить пароль от своего сейфа. Паролем он называет строку, состоящую из строчных латинских букв. Придумав новый пароль, Пуаро хочет убедиться, что его никто не сможет подобрать.
Мсье Бук подсказал ему, что безопасным называется пароль, который не содержит трех или более одинаковых символов подряд, а также никакой символ которого не встречается в ней чаще, чем в половине позиций.
Помогите Пуаро получить из придуманной им строки безопасный пароль при помощи минимального количества операций вида <<заменить -й символ строки на >>.
입력
Входные данные содержит единственную непустую строку, содержащую хотя бы два, но не более, чем символов, состоящую из строчных букв латинского алфавита.
출력
Выведите в единственной строке полученный безопасный пароль.