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' <image> 'y' <image> 'x' <image> 'b' <image> 'a' <image> '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 s1 = t1, s2 = t2, ..., si - 1 = ti - 1, and si < ti.
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public final class PalindromeProblem {

    private static void solve(final Input input, final PrintWriter output) throws IOException {
        char[] inputArray = {'z', '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', 'a'};
        char[] result = input.next().toCharArray();
        char[] outputarray = new char[result.length];
        boolean hasStarted = false;
        for (int i = 0; i < result.length; i++) {
            if (result[i] > inputArray[result[i] - 'a']) {
                outputarray[i] = inputArray[result[i] - 'a'];
                hasStarted = true;
            } else if (hasStarted) {
                for (; i < result.length; i++) {
                    outputarray[i] = result[i];
                }
            } else if (!hasStarted && i == result.length - 1) {
                outputarray[i] = inputArray[0];
            } else {
                outputarray[i] = result[i];
            }
        }
        output.println(new String(outputarray));
    }

    public static void main(String[] args) throws IOException {
        try (final PrintWriter output = new PrintWriter(System.out); final Input input = new Input(new BufferedReader(new InputStreamReader(System.in)))) {
            solve(input, output);
        }
    }

    private static class Input implements Closeable {

        private final BufferedReader in;
        private final StringBuilder sb = new StringBuilder();
        private final static String SEPERATOR = " \n\r\t";

        public Input(final BufferedReader in) {
            this.in = in;
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (SEPERATOR.indexOf(c) == -1) {
                    sb.append((char) c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || SEPERATOR.indexOf(c) != -1) {
                    break;
                }
                sb.append((char) c);
            }
            return sb.toString();
        }

        public void close() throws IOException {
            in.close();
        }
    }
}
