Codeforces 708A Letters Cyclic Shift-白红宇

You are given a non-empty string s consisting of lowercase English letters. You have to pick exactly one non-empty substring of s and shift all its letters 'z' $\text{[math]}$ 'y' $\text{[math]}$ 'x' $\text{[math]}$ 'b' $\text{[math]}$ 'a' $\text{[math]}$ 'z'. In other words, each character is replaced with the previous character of English alphabet and 'a' is replaced with 'z'.

What is the lexicographically minimum string that can be obtained from s by performing this shift exactly once?

Input

The only line of the input contains the string s (1 ≤ |s| ≤ 100 000) consisting of lowercase English letters.

Output

Print the lexicographically minimum string that can be obtained from s by shifting letters of exactly one non-empty substring.

Examples

Input

codeforces

Output

bncdenqbdr

Input

abacaba

Output

aaacaba

Note

String s is lexicographically smaller than some other string t of the same length if there exists some 1 ≤ i ≤ |s|, such that s₁ = t₁, s₂ = t₂, ..., s_i - 1 = t_i - 1, and s_i < t_i.

解题思路:

【题意】

从仅有小写字母组成的字符串s中挑选出一个非空子串

将该子串中的每个字母均替换成前一个字母,如'b'换成'a','c'换成'b',以此类推,特别的,'a'要换成'z'

问经过一次转换之后,字典序最小的字符串s为多少

【类型】

implementation

【分析】

首先,何为字典序最小,大家应该都理解

然后,题目的替换操作,很明显会将字符串s的字典序变小,但是唯一一个特例是字母'a',它替换之后反而会使得字典序变小

于是乎,字母'a'成了突破口,凡是遇到字母'a',能不替换就不替换

也就意味着,我们要替换除'a'之外的其他字母

上述这种,能够替换的有两部分,红色虚线及绿色虚线,从字典序大小考虑出发,越靠前的字母变小,整体字典序越小

所以,我们会替换红色虚线处的字母,而不是绿色虚线处的字母

当然,此题最值得注意的是"exactly one non-empty substring"

这就意味着全'a'串也要变,即字符串"aaaaaaa",我们要替换其中的字母(会使得字典序比原来大),但又要使字典序最小,所以只能将最后一个'a'->'z'

【时间复杂度&&优化】

O(n)

题目链接→

1 #include 
           
             2 using namespace std; 3 int main() 4 { 5     int i,k=0; 6     char s[100005]; 7     gets(s); 8     int len=strlen(s); 9     for(i=0;s[i]!='\0';i++)10         if(s[i]!='a')11             break;12     for(;s[i]!='\0';i++)13     {14         if(s[i]=='a')15             break;16         s[i]--;17         k++;18     }19     if(!k)20         s[strlen(s)-1]='z';21     puts(s);22     return 0;23 }