Wstęp do programowania w C++

Dany jest niepusty ciąg znaków s złożony z małych liter alfabetu łacińskiego. Twoim zadaniem jest wybranie dokładnie jednego niepustego spójnego podciągu ciągu s i przesunięcie wszystkich jego liter: ‘z’ → ‘y’ → ‘x’ → … → ‘b’ → ‘a’ → ‘z’. Innymi słowy każdy znak powinien być zastąpiony przez swego poprzednika w alfabecie łacińskim, a litera ‘a’ jest zastępowana przez ‘z’. Jaki leksykograficznie najmniejszy (najwcześniejszy) ciąg znaków może być otrzymany z s po jednokrotnym wykonaniu opisanej powyżej operacji?

Wejście

Jedyny wiersz danych wejściowych zawiera ciąg znaków s (1 ≤ |s| ≤ 100 000) zawierający wyłącznie małe litery alfabetu łacińskiego.

Wyjście

Program powinien wypisać najwcześniejszy leksykograficznie ciąg znaków powstały w wyniku opisanej wyżej zmiany liter w niepustym spójnym (czyli składającym się ze znaków położonych bezpośrednio obok siebie) podciągu ciągu s.

Example

Input:
koczkodan

Output:
jnbyjncan

Input:
abacaba

Output:
aaacaba