Problem: Mike and Ann are sitting in the classroom. The lesson is boring, so they decided to play an interesting game. Fortunately, all they need to play this game is a string s and a number k (0 ≤ k < |s|).

At the beginning of the game, players are given a substring of s with left border l and right border r, both equal to k (i.e. initially l=r=k). Then players start to make moves one by one, according to the following rules:

  * A player chooses l^{\prime} and r^{\prime} so that l^{\prime} ≤ l, r^{\prime} ≥ r and s[l^{\prime}, r^{\prime}] is lexicographically less than s[l, r]. Then the player changes l and r in this way: l := l^{\prime}, r := r^{\prime}.
  * Ann moves first.
  * The player, that can't make a move loses.



Recall that a substring s[l, r] (l ≤ r) of a string s is a continuous segment of letters from s that starts at position l and ends at position r. For example, "ehn" is a substring (s[3, 5]) of "aaaehnsvz" and "ahz" is not.

Mike and Ann were playing so enthusiastically that they did not notice the teacher approached them. Surprisingly, the teacher didn't scold them, instead of that he said, that he can figure out the winner of the game before it starts, even if he knows only s and k.

Unfortunately, Mike and Ann are not so keen in the game theory, so they ask you to write a program, that takes s and determines the winner for all possible k.

Input

The first line of the input contains a single string s (1 ≤ |s| ≤ 5 ⋅ 10^5) consisting of lowercase English letters.

Output

Print |s| lines.

In the line i write the name of the winner (print Mike or Ann) in the game with string s and k = i, if both play optimally

Examples

Input


abba


Output


Mike
Ann
Ann
Mike


Input


cba


Output


Mike
Mike
Mike

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
void _print(long long t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(long double t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(unsigned long long t) { cerr << t; }
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
long long gcd(long long a, long long b) {
  if (b > a) {
    return gcd(b, a);
  }
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long expo(long long a, long long b, long long mod) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b = b >> 1;
  }
  return res;
}
void extendgcd(long long a, long long b, long long *v) {
  if (b == 0) {
    v[0] = 1;
    v[1] = 0;
    v[2] = a;
    return;
  }
  extendgcd(b, a % b, v);
  long long x = v[1];
  v[1] = v[0] - v[1] * (a / b);
  v[0] = x;
  return;
}
long long mminv(long long a, long long b) {
  long long arr[3];
  extendgcd(a, b, arr);
  return arr[0];
}
long long mminvprime(long long a, long long b) { return expo(a, b - 2, b); }
bool revsort(long long a, long long b) { return a > b; }
void swap(int &x, int &y) {
  int temp = x;
  x = y;
  y = temp;
}
long long combination(long long n, long long r, long long m, long long *fact,
                      long long *ifact) {
  long long val1 = fact[n];
  long long val2 = ifact[n - r];
  long long val3 = ifact[r];
  return (((val1 * val2) % m) * val3) % m;
}
void google(int t) { cout << "Case #" << t << ": "; }
vector<long long> sieve(int n) {
  int *arr = new int[n + 1]();
  vector<long long> vect;
  for (int i = 2; i <= n; i++)
    if (arr[i] == 0) {
      vect.push_back(i);
      for (int j = 2 * i; j <= n; j += i) arr[j] = 1;
    }
  return vect;
}
long long mod_add(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a + b) % m) + m) % m;
}
long long mod_mul(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a * b) % m) + m) % m;
}
long long mod_sub(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (((a - b) % m) + m) % m;
}
long long mod_div(long long a, long long b, long long m) {
  a = a % m;
  b = b % m;
  return (mod_mul(a, mminvprime(b, m), m) + m) % m;
}
long long phin(long long n) {
  long long number = n;
  if (n % 2 == 0) {
    number /= 2;
    while (n % 2 == 0) n /= 2;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      number = (number / i * (i - 1));
    }
  }
  if (n > 1) number = (number / n * (n - 1));
  return number;
}
int cmp(int a, int b) { return a > b; }
int isprime(int N) {
  if (N < 2 || (!(N & 1) && N != 2)) return 0;
  for (int i = 3; i * i <= N; i += 2) {
    if (!(N % i)) return 0;
  }
  return 1;
}
int bin_pow(int ind, int power) {
  if (power == 0) {
    return 1;
  }
  if (power & 1) {
    return ind * bin_pow(ind, power - 1) % 1000000007;
  } else {
    return bin_pow((ind * ind) % 1000000007, power / 2) % 1000000007;
  }
}
int fact(int x) {
  int ret = 1;
  for (int i = 2; i <= x; i++) {
    ret *= i;
    ret %= 1000000007;
  }
  return ret;
}
int ncr(int n, int r) {
  if (r > n) return 0;
  return (fact(n) *
          (bin_pow((fact(r) * fact(n - r)) % 1000000007, 1000000007 - 2))) %
         1000000007;
}
long long maxsubarraysum(long long *array, long long n) {
  long long best = 0, sum = 0;
  for (long long k = 0; k < n; k++) {
    sum = max(array[k], sum + array[k]);
    best = max(best, sum);
  }
  return best;
}
void printBinary(int num) {
  for (int i = 10; i >= 0; --i) {
    cout << ((num >> i) & 1);
  }
  cout << endl;
}
int nPr(int n, int r) { return fact(n) / fact(n - r); }
bool areDigitsSame(int n) {
  vector<int> a;
  while (n > 0) {
    int m = n % 10;
    n = n / 10;
    a.push_back(m);
  }
  for (int i = 0; i < a.size() - 1; i++) {
    if (a[i] != a[i + 1]) {
      return false;
    }
  }
  return true;
}
int binarySearch(vector<int> &arr, int l, int r, int x) {
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (arr[m] == x) {
      return m + 1;
    }
    if (arr[m] < x) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  int min = arr[l] > x ? l : r;
  ++min;
  return min;
}
void letsNetflixAndChill() {
  long long i, j, l = 0, m, n, k;
  string s;
  char ch = 'z' + 1;
  cin >> s;
  for (auto it : s) {
    if (it > ch) {
      cout << "Ann"
           << "\n";
    } else {
      ch = it;
      cout << "Mike"
           << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  auto start1 = high_resolution_clock::now();
  int t = 1;
  while (t--) {
    letsNetflixAndChill();
  }
  auto stop1 = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop1 - start1);
  return 0;
}