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' $\rightarrow$ 'y' $\rightarrow$ 'x' $\rightarrow \ldots \rightarrow$ 'b' $\rightarrow$ 'a' $\rightarrow$ '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_1 = t_1, s_2 = t_2, ..., s_{i} - 1 = t_{i} - 1, and s_{i} < t_{i}.

Difficulty: competition

Starter code:

Solutions:
#!/usr/bin/env python3

import re

try:
    while True:
        s = input()
        m = re.search(r"[^a]", s)
        if m is None:
            print(s[:-1], end="z\n")
        else:
            j = s.find('a', m.end())
            if j == -1:
                j = len(s)
            print(end=s[:m.start()])
            for i in range(m.start(), j):
                print(end=chr((ord(s[i]) - 98) % 26 + 97))
            print(s[j:])

except EOFError:
    pass


# -*- coding: utf-8 -*-
"""
Created on Wed Aug 24 13:19:53 2016

@author: Felicia
"""

s = input()
n = len(s)
hea = -1
tai = -1
new = list(s)

for i in range(n):
    if new[i]!='a':
        hea = i
        for j in range(i+1,n):
            if new[j]=='a':
                tai = j-1
                break
        else:
            tai = n-1
        for k in range(hea,tai+1):
            temp = ord(new[k])-1
            new[k] = chr(temp)
        break

if hea ==-1:
    new[n-1] = 'z'
    
news = ''.join(new)
print(news)


def shift():
    word = input()
    i = 0
    shifted = ''
    while i < len(word) - 1:
        if word[i] != 'a':
            break
        shifted += word[i]
        i += 1
    if i == len(word) - 1 and word[i] == 'a':
        shifted += 'z'
        return shifted
    while i < len(word):
        if word[i] == 'a':
            shifted += word[i:]
            break
        shifted += chr(ord(word[i]) - 1)
        i += 1
    return shifted

print(shift())


st = input()
st1 = ""
others = False
length = len(st)
for i in range(0, length):
    if i == length - 1 and others is False:
        st1 += str(chr(((ord(st[i]) - 98) % 26) + 97))
        break
    if st[i] == 'a':
        if others is True:
            st1 += st[i:length]
            break
        st1 += str(st[i])
    else:
        others = True
        st1 += str(chr(ord(st[i]) - 1))
print(st1)


s = input()
table = "abcdefghijklmnopqrstuvwxyz"


def nextchar(x):
    index = table.index(x)
    return table[index - 1]
ans, start = "", 0
for i in range(len(s)):
    if s[i] != 'a':
        ans += nextchar(s[i])
        start = 1
        continue
    if s[i] == 'a' and start == 1:
        ans += s[i:len(s)]
        break
    ans += s[i]
if str(s).count('a') == len(s):
    ans = str(s)[0:len(s) - 1] + "z"
print(ans)

import sys

def shl(s, be, en):
    t = s[:be];
    for i in range(be, en):
        if s[i]=='a':
            t += 'z'
        else:
            t += chr(ord(s[i])-1)
    return t+s[en:]

s = input()
i = 0
L = len(s)
while i<L and s[i]=='a':
    i += 1
if i==L:
    print(s[:L-1]+'z')
    return
    
j = i+1
while j<L and s[j]!='a':
    j += 1
print(shl(s,i,j))


def findNot(string, char):
    for i in range(len(string)):
        if string[i] != char:
            return i
    return len(string) - 1

s = input()
beg = findNot(s, "a")
res = s[0:beg]
for i in range(beg, len(s)):
    if i != beg and s[i] == "a":
        res += s[i:]
        break
    if s[i] == "a":
        res += "z"
    else:
        res += chr(ord(s[i]) - 1)
print(res)

letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g','h', 'i', 'j', 'k', 'l', 'm', 'n', \
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

dataIn = str(input())
data = []
for i in dataIn:
    data.append(i)

count = 0
begin = 0

if len(data) == 1:
    if data[0] == 'a':
        data[0] = 'z'
    else:
        for j in range(len(letters)):
            if letters[j] == data[0]:
                data[0] = letters[j-1]
else:
    i = 0
    begin = False
    while i < len(data) - 1:
        if data[i] == 'a':
            i += 1
        else:
            break
    for k in range(i, len(data)):
        if data[k] == 'a' and k != len(data) - 1:
            break
        elif data[k] == 'a' and k == len(data) -1:
            if not begin: data[k] = 'z'
        else:
            begin = True
            for j in range(len(letters)):
                if letters[j] == data[k]:
                    data[k] = letters[j-1]

result = ''
for i in data:
    result += i

print(result)


letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g','h', 'i', 'j', 'k', 'l', 'm', 'n', \
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

dataIn = str(input())
data = []
for i in dataIn:
    data.append(i)

count = 0
begin = 0

if len(data) == 1:
    if data[0] == 'a':
        data[0] = 'z'
    else:
        for j in range(len(letters)):
            if letters[j] == data[0]:
                data[0] = letters[j-1]
else:
    i = 0
    begin = False
    while i < len(data) - 1:
        if data[i] == 'a':
            i += 1
        else:
            break
    for k in range(i, len(data)):
        if data[k] == 'a' and k != len(data) - 1:
            break
        elif data[k] == 'a' and k == len(data) -1:
            if not begin: data[k] = 'z'
        else:
            begin = True
            for j in range(len(letters)):
                if letters[j] == data[k]:
                    data[k] = letters[j-1]

result = ''.join(data)


print(result)


s = input()
t = ""

l = len(s)
a = 'a' * l

if s == a:
    t = 'a' * (l-1) + 'z'
else:
    i = 0
    while i < l:
        if s[i] == 'a':
            t += 'a'
        else:
            break
        i += 1

    while i < l:
        if s[i] != 'a':
            t += str(chr(ord(s[i]) - 1))
        else:
            break
        i += 1

    while i < l:
        t += str(s[i])
        i += 1

print(t)



s = list(input())

f = False
c = False

for i in range(len(s)):
	ss = s[i]
	if ss == 'a':
		if f is True:
			print(''.join(s))
			return
		else:
			continue
	else:
		s[i] = chr(ord(ss)-1)
		f = True
		c = True
		
if c is False:
	s[-1] = 'z'

print(''.join(s))

def change (c):
    if c == 'a':
        return 'z'
    else:
        return chr(ord(c)-1)

s = list(input())
L = len(s)
flag = False
for i in range(L-1):
    if s[i] != 'a':
        flag = True
        while i < L:
            if s[i] == 'a':
                break
            s[i] = change(s[i])
            i = i + 1
        break
    
if not flag:
    s[L-1] = change(s[L-1])

print(''.join(s))


s=list(input())
i=f=0
while(i<len(s)):
	while(i<len(s) and s[i]!='a'):
		s[i]=chr(ord(s[i])-1)
		f=1
		i+=1
	if(f):
		break
	i+=1
if(f==0):
	s[len(s)-1]='z'
print("".join(s))


def __starting_point():
    refer_dict = {
        'a': 'z',
        'b': 'a',
        'c': 'b',
        'd': 'c',
        'e': 'd',
        'f': 'e',
        'g': 'f',
        'h': 'g',
        'i': 'h',
        'j': 'i',
        'k': 'j',
        'l': 'k',
        'm': 'l',
        'n': 'm',
        'o': 'n',
        'p': 'o',
        'q': 'p',
        'r': 'q',
        's': 'r',
        't': 's',
        'u': 't',
        'v': 'u',
        'w': 'v',
        'x': 'w',
        'y': 'x',
        'z': 'y',
    }
    s = str(input())
    line = s.split('a')
    size = len(line)
    flag = True
    for it in range(size):
        if line[it] != '':
            temp = str()
            for i in line[it]:
                temp += refer_dict[i]
            line[it] = temp
            flag = False
            break
    if flag:
        print(s[:-1] + 'z')
    else:
        print('a'.join(line))

__starting_point()

s=input()
n=len(s)
p=list(s)
i=0
while(s[i]=='a'):
    i+=1
    if i==n:
        p[n-1]='z'
        s="".join(p)
        print(s)
        return
while(s[i]!='a'):
    p[i]=chr(ord(s[i])-1)
    i+=1
    if i==n:
        break
s="".join(p)
print(s)


#in the nmae of god
#Mr_Rubik
refer_dict = {'a': 'z','b': 'a','c': 'b','d': 'c','e': 'd','f': 'e','g': 'f','h': 'g','i': 'h','j': 'i','k': 'j','l': 'k','m': 'l','n': 'm','o': 'n','p': 'o','q': 'p','r': 'q','s': 'r','t': 's','u': 't','v': 'u','w': 'v','x': 'w','y': 'x','z': 'y',}
s=str(input())
line=s.split('a')
size=len(line)
flag=True
for it in range(size):
    if line[it] != '':
        temp = str()
        for i in line[it]:
            temp += refer_dict[i]
        line[it] = temp
        flag = False
        break
if flag:
    print(s[:-1] + 'z')
else:
    print('a'.join(line))

# print("Input the string")
st = input()

if st == 'a':
    print('z')
else:
    apos = st.find('a')
    if apos == -1:
        #  No as in the word at all--shift everything down
        answerlist = []
        for ch in st:
            newch = chr(ord(ch)-1)
            answerlist.append(newch)
        print(''.join(answerlist))
    elif apos > 0:
        #  Shift everything up to the first a
        answerlist = []
        for i in range(0, apos):
            newch = chr(ord(st[i])-1)
            answerlist.append(newch)
        print(''.join(answerlist) + st[apos:])
    else:
        #  The hard case--it starts with an a
        #  Find the first non-a
        pos = 1
        while pos < len(st) and st[pos] == 'a':
            pos += 1
        if pos == len(st):  # All letters are a--must change last letter to z
            print(st[0:len(st)-1] + 'z')
        else:
            # Change everything from pos to the next a
            nextapos = st.find('a', pos+1)
            if nextapos == -1:  # No more as--change to the end
                answerlist = []
                for i in range(pos, len(st)):
                    newch = chr(ord(st[i])-1)
                    answerlist.append(newch)
                print(st[0:pos] + ''.join(answerlist))
            else:   # Change everything between pos and nextapos
                answerlist = []
                for i in range(pos, nextapos):
                    newch = chr(ord(st[i])-1)
                    answerlist.append(newch)
                print(st[0:pos] + ''.join(answerlist) + st[nextapos:])
             
            
        
        


s = list(input())


f = False
for i in range(len(s)):
    
    if s[i] != "a":
        s[i] = chr(ord(s[i]) - 1)
        f = True
    else:
        if f:
            break
        elif i == len(s) - 1:
            s[i] = "z"

print("".join(s))


s=list(input())
a=0
if set(s)=={'a'}: s[-1]='{'
for i in range(len(s)):
   if a==0:
      if s[i]=='a': continue
      else:
         s[i]=chr(ord(s[i])-1)
         a=1
   else:
      if s[i]=='a': break
      else:
         s[i]=chr(ord(s[i])-1)
print(''.join(s))

import sys
n = input()
i=0
n=n+'a'
m=""
while n[i]=="a" and len(n)>i+1:
    i+=1
    m=m+'a'
if i+1==len(n):
    w=m[0:len(m)-1]+'z'
    print(w)
    return
while n[i]!="a" and len(n)>i:
    m=m+chr(ord(n[i])-1)
    i+=1
m=m+n[i:len(n)-1]

print(m)

import sys
slowo = input()
slowo=slowo+'a'
ret = ""
i =0
while slowo[i]=="a" and len(slowo)>i+1:
    i+=1
    ret+='a'
if i+1==len(slowo):
    w=slowo[0:len(slowo)-2]+'z'
    print (w)
    return
while slowo[i]!='a' and len(slowo)>i:
    ret=ret+chr(ord(slowo[i])-1)
    i+=1
ret=ret+slowo[i:len(slowo)-1]
print(ret)

import sys
a = list(input())
b = ""
l = 0
o = 0
for x in range (len(a)):

    if a[x] == 'a' and l == 1:
        break
    elif a[x] != 'a':
        a[x] = chr(ord(a[x])-1)
        l = 1
        o = 1

if o == 0:
    a[len(a)-1] = "z"
print("".join(a))

import sys
n=input()
i=0
n=n+'a'
m=""
while n[i]=='a' and len(n)>i+1:
    i+=1
    m=m+'a'
if i+1==len(n):
    w=m[0:len(m)-1]+'z'
    print(w)
    return
while n[i]!='a' and len(n)>i:
    m=m+chr(ord(n[i])-1)
    i+=1
m=m+n[i:len(n)-1]

print(m)


S=input().split('a')
ma=1000000000000
R='abcdefghijklmnopqrstuvwxyz'
for x in S :
    if len(x)>0 :
        ma=len(x)
        break
S1=''
c=1
p=len(S)
for x in S :
    if len(x)==ma and c==1 :
        c=0
        for i in range(len(x)) :
            S1=S1+R[R.index(x[i])-1]
    else :
        S1=S1+x
    if p!=1 :
        S1=S1+'a'
        p=p-1
    
if S1.count('a')==len(S1) and c==1 :
    S1=S1[:len(S)-2]+'z'
print(S1)
    
        
    


'''input
aaaaaaaaaa
'''
def lexi_sum(s):
	a = "abcdefghijklmnopqrstuvwxyz"
	t = 0
	for l in s:
		t += a.index(l) + 1
	return t
def shift(s):
	a = "abcdefghijklmnopqrstuvwxyz"
	s1 = ""
	for l in s:
		s1 += a[a.index(l)-1]
	return s1
s = input()
if set(s) == set("a"):
	print(s[:-1] + "z")
	quit()
s = s.split("a")
m = s[0]
k = 1
while len(m) < 1:
	m = s[k]
	k += 1
m1 = s.index(m)
s[m1] = shift(m)
print("a".join(s))