题目描述

Mike和Ann坐在教室里。这课很无聊，所以他们决定玩一个有趣的游戏。幸运的是，他们只需要一个字符串s和一个数字k（$0 \leq k < |s|$）。

在游戏开始时，给玩家一个子串s，左边框l和右边框r都等于k（即最初l=r=k）。然后玩家开始按照以下规则逐一移动：

1.玩家选择L和R，使得$L≤l，R≥r$和s[L，R]在字典序上小于s[l，r]。然后玩家以这种方式改变l和r, $l:= L，r:= R$(:= 为赋值号)。

2.Ann先动。

3.不能移动的玩家输了。

回想一下，字符串s的子串s[l，r]（$l ≤ r$）是s中从位置l开始到位置r结束的连续字母段。例如，"ehn"是"aaaehnsvz"(s[3,5]), 而"ahz"不是。

Mike和Ann玩得如此热情，以至于他们没有注意到老师走近了他们。令人惊讶的是，老师没有责骂他们，而是说，即使他只知道S和K，他也能在比赛开始前找出胜利者。

不幸的是，Mike和Ann对博弈论不太感兴趣，所以他们要求你写一个程序，用s来决定所有可能k的赢家。

可以尝试一下给两个字符串一些值,用"<"比较一下大小，字符串的大小是按照字典序的大小

输入格式

输入的第一行包含由小写英文字母组成的单个字符串s。

输出格式

打印$|s|$行 （$|s|$为字符串s的长度）

在这行中，我用字符串s和k=i写下游戏中胜利者的名字（打印Mike或Ann)

样例

样例输入

abba

样例输出

Mike
Ann
Ann
Mike

数据范围与提示

$1 \leq s \leq 5 \ast 10^5$