Lexicographically Smallest String After Substring Operation

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Original prompt

You are given a string s consisting of lowercase English letters.

You must choose a non-empty substring and perform the following operation on each character in that substring exactly once: replace it with the previous letter in the alphabet (e.g., b -> a, c -> b). Note that the previous letter of a is z.

Return the lexicographically smallest string you can obtain after performing the operation once.

I/O

Input: one line string s Output: one line string, the lexicographically smallest result

Constraints

1 <= len(s) <= 1e5 s contains only a to z

Examples

Input: cbabc Output: baabc Input: aaaa Output: zzzz Input: leetcode Output: kddsbncd

Complete solveLexicographicallySmallestSubstringOperation. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.