103685: [Atcoder]ABC368 F - Dividing Game

Problem Statement

You are given a sequence of $N$ positive integers $A = (A_1, A_2, \dots ,A_N)$, where each element is at least $2$. Anna and Bruno play a game using these integers. They take turns, with Anna going first, performing the following operation.

• Choose an integer $i \ (1 \leq i \leq N)$ freely. Then, freely choose a positive divisor $x$ of $A_i$ that is not $A_i$ itself, and replace $A_i$ with $x$.

The player who cannot perform the operation loses, and the other player wins. Determine who wins assuming both players play optimally for victory.

Constraints

• $1 \leq N \leq 10^5$
• $2 \leq A_i \leq 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print Anna if Anna wins the game, and Bruno if Bruno wins.

Sample Input 1

3
2 3 4

Sample Output 1

Anna

For example, the game might proceed as follows. Note that this example may not necessarily represent optimal play by both players:

• Anna changes $A_3$ to $2$.
• Bruno changes $A_1$ to $1$.
• Anna changes $A_2$ to $1$.
• Bruno changes $A_3$ to $1$.
• Anna cannot operate on her turn, so Bruno wins.

Actually, for this sample, Anna always wins if she plays optimally.

Sample Input 2

4
2 3 4 6

Sample Output 2

Bruno

问题陈述

给定一个由N个正整数组成的序列A = (A_1, A_2, …, A_N)，其中每个元素至少为2。安娜和布鲁诺用这些整数玩游戏。他们轮流进行，安娜先开始，执行以下操作。

• 自由选择一个整数i（1≤i≤N）。然后，自由选择一个不是A_i本身的A_i的正除数x，并用x替换A_i。

无法进行操作的玩家输掉比赛，另一位玩家获胜。假设两位玩家都为了胜利而进行最佳操作，确定获胜者。

约束条件

• 1≤N≤10^5
• 2≤A_i≤10^5
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

N
A_1 A_2 … A_N

输出

如果安娜赢得游戏，打印Anna，如果布鲁诺赢得游戏，打印Bruno。

样本输入1

3
2 3 4

样本输出1

Anna

例如，游戏可能以下列方式进行。请注意，此示例可能不一定代表两位玩家的最佳操作：

• 安娜将A_3改为2。
• 布鲁诺将A_1改为1。
• 安娜将A_2改为1。
• 布鲁诺将A_3改为1。
• 安娜在她的回合无法操作，所以布鲁诺获胜。

实际上，对于这个样本，如果安娜进行最佳操作，她总是获胜。

样本输入2

4
2 3 4 6

样本输出2

Bruno