/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 475 点
問題文
各要素が 2 以上である長さ N の正整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。Anna と Bruno はこれらの整数を用いてゲームをします。二人は、 Anna を先手として交互に以下の操作を行います。
- 整数 i \ (1 \leq i \leq N) を自由に選ぶ。A_i の正の約数であって A_i 自身でないものを自由に選び x とし、 A_i を x で置き換える。
操作が行えなくなった方が負けで、負けなかった方が勝ちです。両者が勝ちを目指して最適な行動を取るとき、どちらが勝つか判定してください。
制約
- 1 \leq N \leq 10^5
- 2 \leq A_i \leq 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
Anna がゲームに勝つ場合 Anna と、 Bruno がゲームに勝つ場合 Bruno と出力せよ。
入力例 1
3 2 3 4
出力例 1
Anna
例えば、ゲームの進行として以下のようなものが考えられます。必ずしも両者が最適な行動を取った例とは限らないことに注意してください。
- Anna が A_3 を 2 にする。
- Bruno が A_1 を 1 にする。
- Anna が A_2 を 1 にする。
- Bruno が A_3 を 1 にする。
- Anna のターンで操作ができないので Bruno の勝ちとなる。
実際には、このサンプルでは Anna が最適に行動すると常に Anna が勝つことができます。
入力例 2
4 2 3 4 6
出力例 2
Bruno
Score : 475 points
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