CF1220C.Substring Game in the Lesson

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

游戏开始时，玩家会得到 $s$ 的一个子串，其左边界 $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}$。
• Ann 先手。
• 不能进行操作的玩家判负。

回忆一下，字符串 $s[l, r]$（$l \le r$）是字符串 $s$ 的一个子串，表示从位置 $l$ 到 $r$ 的连续字母。例如，"ehn" 是 "aaaehnsvz" 的一个子串（$s[3, 5]$），而 "ahz" 不是。

Mike 和 Ann 玩得太投入了，以至于没有注意到老师走近了他们。令人惊讶的是，老师没有批评他们，反而说他可以在游戏开始前，仅凭 $s$ 和 $k$ 就能判断谁会获胜。

不幸的是，Mike 和 Ann 并不擅长博弈论，于是他们请求你写一个程序，输入 $s$，输出对于所有可能的 $k$，谁会获胜。

输入的第一行包含一个字符串 $s$（$1 \leq |s| \leq 5 \cdot 10^5$），仅由小写英文字母组成。

输出 $|s|$ 行。

第 $i$ 行输出在字符串 $s$ 和 $k=i$ 的情况下，若双方都采取最优策略，游戏的获胜者（输出 Mike 或 Ann）。

由 ChatGPT 4.1 翻译