Миша и Аня сидят на скучном уроке. Чтобы хоть как-то скрасить ожидание перемены, они придумали интересную игру. Для игры необходима лишь строка \(s\) и число \(k\) (\(0 \le k < |s|\)).
Игра начинается с того, что на строке \(s\) отмечается подстрока длины 1, ее левая граница \(l\) и правая граница \(r\) равны \(k\) (то есть вначале игры \(l=r=k\)). Далее игроки ходят по очереди, расширяя подстроку по следующим правилам:
- Игрок выбирает индексы \(l^{\prime}\) и \(r^{\prime}\) такие, что \(l^{\prime} \le l\), \(r^{\prime} \ge r\) и \(s[l^{\prime}, r^{\prime}]\) лексикографически меньше \(s[l, r]\). После этого изменяет значения \(l\) и \(r\) следующим образом: \(l := l^{\prime}\), \(r := r^{\prime}\).
- Аня ходит первой.
- Проигрывает тот, кто не может сделать ход.
Напомним, что подстрокой \(s[l, r]\) (\(l \le r\)) строки \(s\) будем называть непрерывную подпоследовательность символов начинающуюся в позиции \(l\) и заканчивающуюся в позиции \(r\). Например «ehn» — подстрока (\(s[3, 5]\)) строки «aaaehnsvz», а «ahz» — нет.
Миша и Аня играли в игру так увлеченно, что не заметили как к ним подошел учитель. К большому удивлению обоих, он не стал их отчитывать, а сказал, что может определить победителя до начала игры, зная лишь \(s\) и \(k\)!
К сожалению, Миша и Аня не разбираются в теории игр, поэтому попросили Вас написать программу, которая по заданной \(s\) определяет победителя для всех возможных \(k\).
Выходные данные
Выходные данные должны содержать \(|s|\) строк.
В строке номер \(i\) выведите имя победителя игры (выведите Ann или Mike) со строкой \(s\), для \(k = i\), при условии, что Аня и Миша играют оптимально.