暂无测试数据。

蒜头君和花椰妹最近刚学会了字符串的字典序大小比较。他们想要通过一个游戏证明谁更聪明。

游戏最初给出一个只包含小写英文字母的字符串，字符串中的每一个字母最多可以被两个人中的一个替换为其他小写英文字母（即：字符串中的每个字母只能被替换一次，并且新替换的字母不可以和原字母相同）。

已知：

• 蒜头君想要通过替换让字符串尽可能的小；
• 花椰妹想要通过替换让字符串尽可能的大；

并且蒜头君和花椰妹依次交替替换字母，并且每次只能替换一个字母，由蒜头君最先进行替换，直到不能替换为止（操作顺序为：蒜头君 - 花椰妹 - 蒜头君 - 花椰妹 - $\cdots$）。

蒜头君和花椰妹都非常聪明，每次都会选择最优的操作，那么最终的字符串是怎样的呢（答案唯一）？

字典序：字典序是从左到右开始进行逐字符比较。

• 如果当前比较的两个字符一样，则继续向后比较。
• 若当前比较的两个字符不同，则哪一个字符小，则该字符串的字典序小；
• 一旦出现某一个字符串的所有字符都已经经过比较，而另一个字符串还存在未被比较的字符时，较短的字符串更小；

输入格式

输入共一行，一个只包含小写英文字母的字符串 $str$，且 $str$ 的长度为 $len(1\leq len \leq 1000)$。

输出格式

输出共一行，为 $str$ 经过蒜头君和花椰妹的最优操作后的结果。

jisuanke

azazbzaz

abcde

bzaza

bzfa

ayaz