给你一个由小写英文字母组成的非空字符串 s 。您必须选择 s 的一个非空子串,并移动其所有字母 'z' $$\rightarrow$$ 'y' $$\rightarrow$$ 'x' $$\overrightarrow { a }, \ldots, \overrightarrow { a }$$ 'b' $$\rightarrow$$ 'a' $$\rightarrow$$ 'z'。换句话说,每个字符都被替换为英文字母表中的前一个字符,并且“a”被替换为“z”。
通过执行一次此移位,可以从 s 获得按字典顺序排列的最小字符串是多少?
输入
输入中唯一一行包含由小写英文字母组成的字符串 s (1 ≤ |s| ≤ 100 000)。
输出
打印按字典顺序排列的最小字符串,该字符串可以通过移动恰好一个非空子字符串的字母来从 s 获得。
示例
输入 #1
codeforces
输出 #1
bncdenqbdr
输入 #2
abacaba
输出 #2
aaacaba
注意
如果存在 1 ≤ i ≤ |s|,使得 s1 = t1、s2 = t2、...、si - 1 = ti - 1 且 si < ti,则字符串 s 按字典顺序小于相同长度的其他字符串 t。