1372: Natsume's Book of Friends

$Madara$ 在教 $Natsume$ 玩《友人帐》，以提高他的思维，帮助他想出归还妖怪名字的策略。这个游戏的规则非常简单：

• 游戏开始于有 $n$ 页的友人帐，索引从 $1$ 到 $n$。第 $i$ 页包含 $s_i$ 个妖怪名字。
• 玩家轮流移动。从一堆名字中移除一定数量的名字被认为是一次移动。移除 $0$ 个名字不算作一步移动。
• 无法移动的玩家将输掉游戏。

现在 $Natsume$ 为自己已经准备好归还名字了，但 $Madara$ 不这么想。为了证明自己的观点，$Madara$ 议他们玩一个进阶版的游戏。

在这个进阶版中，对同一页的名字不能执行完全相同的操作。例如，如果从某页中的名字中移除了 $4$ 个，那么之后就不能再次从该页中移除 $4$ 个名字。

$Madara$ 布置好游戏并先手行动。$Natsume$ 认为 $Madara$ 只是想借此阻止他去归还妖怪名字。$Natsume$ 想知道，如果双方都采取最优策略，他是否能够获胜

第一行由单个整数 $n$ 组成-友人帐的页数。

接下来的 $n$ 行中，每行都包含一个整数 $s_i$ -第 $i$ 页中的名字数量。

$1 \le n \le 10^6$，$1 \le s_i \le 10^{18}$

如果 $Natsume$ 能获胜，则打印 “$Natsume$”（不带引号），否则打印 “$Madara$”（不带引号）

2
1
2

Natsume