输入一个长度不超过100000的非空字符串s，从其中抽取出一个非空子串t，将t中除了’a’以外的字母全部变小一个，即’z’变为’y’，’y’变为’x’，依次类推，’b’变为’a’，额外的将’a’变为’z’，最后将变换后的t串放回到s串中原来所在的位置，得到新的字符串s’。现在对于给定的s，只能选其中的一个子串t，对t中的所有字母变换一次，求这样操作能够得到的字典序最小的s’。

【备注】

字典序：两个字符串A和B比较大小，先比较第一个字符，如果A中的第一个字母比B中的第一个字母小，则字典序中A排在B的前面；反之，如果A中的第一个字母比B中的第一个字母大，则字典序中B排在A的前面；如果A中的第一个字母和B中的第一个字母一样，则继续比较第二个；依次类推。比如”abcd”比”abcde”小，”abcdef”比”abdcb”小。

输入文件名为change.in。

输入文件只有一行，一个长度不超过100000的仅包含小写字母的非空字符串s。

输出文件名为change.out。

输出文件只有一行，包含一个经过变换后得到的字典序最小的字符串。

abacaba

aaacaba

样例1说明：选择第2个字母’b’作为子串，将其变换为’a’

样例2输入

aaaaaa

样例2输出

aaaaaz

样例3输入

aaabcdbcdaaaaa

样例3输出

aaaabcabcaaaaa

样例3说明：选择第4个字母到第9个字母作为子串，将其变换为abcabc，替换到原来的字符串中

【数据规模与约定】

对于50%的数据，输入的字符串长度不超过100

对于100%的数据，输入的字符串长度不超过100000