配点: 100点
問題文
东京工业大学的学生小安正在和小爱玩一种名为“拿石头”游戏的两人游戏,但她对此感到厌倦,因为她知道获胜公式。
因此,安妮想出了一个专注于素数的游戏,并将其命名为“素数游戏”。
素数游戏规则如下。
- 在开始时 有 N 山,i 第二座山是 X_i 個(X_i 是质数)
- 两名玩家轮流选择其中一堆装有石子的石子,并从中取出一些石子。
- 一次可以取的石子数是质数,堆中剩余的石子数也是 必须是 0 或素数
- 第一个无法拿走任何石子的玩家失败。
这是一条新规则,但小安和小爱似乎立刻就想出了获胜的方法。
所以小安是第一推动者,小爱是第二推动者。 由 X_1 個, X_2 個, \ldots , X_N 石头组成 N 当玩素数游戏时,有一堆
制約
- 所有输入均为整数
- 1 \le N \le 2 \times 10^5
- 2 \le X_i \le 10^6
- X_i 是质数 答案可以由
入力
输入是按以下格式从标准输入给出的。
N X_1 X_2 \ldots X_N
出力
如果先走的安酱获胜 An如果抽奖的小爱获胜 Ai 。
入力例 1
1 13
出力例 1
An
- Ann-chan,第一个玩家,首先从山上开始。 只需拿走所有 13 碎片即可。
入力例 2
2 17 13
出力例 2
An
- 第一位玩家小安从第二座山开始。 如果你拿走 2 棋子,抽签的爱酱只能拿走第一堆或第二堆中的所有东西,所以安酱获胜。
入力例 3
6 49529 868033 52361 519803 19289 386501
出力例 3
Ai