Decryption of cyclic string shift

Swift Hard strings

Task «Decryption of cyclic string shift»

Given an encrypted string S consisting of lowercase Latin letters. It was obtained from the original string T by a cyclic shift to the right by some number of positions k (0 ≤ k < |T|) and then replacing each character with the next one in the alphabet (with cyclic wrap: 'z' → 'a'). It is necessary to find the original string T of minimal length such that after the described transformation, S is obtained. If there are several such T, choose the lexicographically smallest one. The length of S is from 1 to 1000. It is guaranteed that a solution exists.

Input Format

One string S (lowercase Latin letters, length from 1 to 1000).

Output Format

One line — the original string T of minimum length (and lexicographically minimal among such).

Examples

Example 1

INPUT

za

OUTPUT

yz

Example 2

INPUT

aaa

OUTPUT

z

Example 3

INPUT

5
3
0

OUTPUT

None

main.swift