Условие:
Сегодня Манас изучает криптографию и экспериментирует со своим любимым алгоритмом шифрования.
Пусть дана строка s длины n. Алгоритм строит строку t длины n следующим образом. Для каждого i (1≤i≤n) рассматривается префикс s1s2…si и выбирается символ ti, который встречается в этом префиксе максимальное число раз. Если таких символов несколько, можно выбрать любой из них.
Полученная строка t считается зашифрованной версией строки s.
Из-за неоднозначности выбора при равенстве частот по строке t нельзя однозначно восстановить s.
Вам дана строка t. Восстановите любую строку s, которая могла привести к t при описанном алгоритме. Если подходящих строк несколько, выведите любую.
