此题和上一题只有数据范围不同^-^
小Maoge正在和maoge玩游戏。游戏规则是这样的： 每次一个人可以对给出的数进行分割，将其割成两个非零自然数，之后由另一个人选择留下两个数中的其中一个；之后由另一个人进行分割这个剩下的数，重复步骤...当一个人无法对数进行分割的时候游戏结束，另一个人获胜。
现在要你求出游戏的胜败。每局由小Maoge先进行分割，如小Maoge赢输出"sMg wins" 如果zs赢输出"mg wins"
我们假设双方都是绝顶聪明的，也就是每个人都按最佳步骤来分割。
一个数M，表示初始的数（0<=M<=10000）
输出一串字符 表示游戏结果
2
sMg wins