#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:64000000")
const int infi = 1e9 + 7;
const long long infl = 1e18;
inline int readChar();
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void flush();
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c >= 0 && c <= 32) c = getChar();
  return c;
}
inline int readWord(char *bf) {
  char *cur = bf;
  *cur = getChar();
  while (*cur <= 32) *cur = getChar();
  while (*cur > 32) {
    ++cur;
    *cur = getChar();
  }
  return cur - bf;
}
inline int readInt() {
  int s = 1, c = readChar();
  int x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = x;
}
inline void flush() {
  if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
inline void writeInt(long long x) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n--) writeChar(s[n]);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
string ar;
int main() {
  ios_base::sync_with_stdio(0);
  cin.sync_with_stdio(false);
  cin.tie(0);
  cin >> ar;
  string arz;
  int flag = 0;
  int n = (int)ar.size();
  for (int i = 0; i < n; ++i) {
    if (ar[i] != 'a') {
      if (!flag) {
        ar[i]--;
        flag = 1;
        continue;
      } else {
        ar[i]--;
      }
    } else {
      if (flag) break;
    }
  }
  if (flag == 0) {
    if (ar[n - 1] == 'a')
      ar[n - 1] = 'z';
    else
      ar[n - 1]--;
  }
  cout << ar;
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:64000000")
const int infi = 1e9 + 7;
const long long infl = 1e18;
inline int readChar();
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void flush();
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c >= 0 && c <= 32) c = getChar();
  return c;
}
inline int readWord(char *bf) {
  char *cur = bf;
  *cur = getChar();
  while (*cur <= 32) *cur = getChar();
  while (*cur > 32) {
    ++cur;
    *cur = getChar();
  }
  return cur - bf;
}
inline int readInt() {
  int s = 1, c = readChar();
  int x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = x;
}
inline void flush() {
  if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
inline void writeInt(long long x) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n--) writeChar(s[n]);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
string ar;
int main() {
  ios_base::sync_with_stdio(0);
  cin.sync_with_stdio(false);
  cin.tie(0);
  cin >> ar;
  string arz;
  int flag = 0;
  int n = (int)ar.size();
  for (int i = 0; i < n; ++i) {
    if (ar[i] != 'a') {
      if (!flag) {
        ar[i]--;
        flag = 1;
        continue;
      } else {
        ar[i]--;
      }
    } else {
      if (flag) break;
    }
  }
  if (flag == 0) {
    if (ar[n - 1] == 'a')
      ar[n - 1] = 'z';
    else
      ar[n - 1]--;
  }
  cout << ar;
  return 0;
}

```