迈克和安坐在教室里。这堂课很无聊,所以他们决定玩一个有趣的游戏。幸运的是,玩这个游戏他们只需要一个字符串 $$$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}$$$。
- 安先行动。
- 无法移动的玩家失败。
回想一下,字符串 $$$s$$$ 的子串 $$$s[l, r]$$$ ($$$l \le r$$$) 是 s 中从位置 $$$l$$$ 开始到位置 $$$r$$$ 结束的连续字母段。例如,“ehn”是“aaaehnsvz”的子字符串 ($$$s[3, 5]$$$),而“ahz”不是。
迈克和安玩得如此热情,以至于他们没有注意到老师走近他们。令人惊讶的是,老师并没有责骂他们,而是说,即使他只知道$$$s$$$和$$$k$$$,他也能在比赛开始前就猜出胜负。
不幸的是,Mike 和 Ann 对博弈论不太热衷,所以他们要求你编写一个程序,该程序需要 $$$s$$$ 并确定所有可能的 $$$k$$$ 的获胜者。
输入
输入的第一行包含一个由小写英文字母组成的字符串 $$$s$$$ ($$$1 \leq |s| \leq 5 \cdot 10^5$$$)。
输出
打印 $$$|s|$$$ 行。
在 $$$i$$$ 行中用字符串 $$$s$$$ 写入游戏中获胜者的名字(打印出 Mike 或 Ann),并且 $$$k = i$$$(如果两者都发挥最佳)
示例
输入 #1
abba
输出 #1
Mike Ann Ann Mike
输入 #2
cba
输出 #2
Mike Mike Mike