← 返回题目列表

Codeforces · 708/A

A. 字母循环移位

中文机器翻译题面 查看原题

给你一个由小写英文字母组成的非空字符串 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。