Nim without Zero

여러 더미에서 돌을 가져가되 더미 크기의 XOR을 0으로 만든 사람이 지는 게임에서 최선의 플레이를 할 때 승자를 판정한다.

어려움8게임 이론수학비트 연산아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

Alice: "Hi, Bob! Let's play Nim!"

Bob: "Are you serious? I don't want to play it. I know how to win the game."

Alice: "Right, there is an algorithm to calculate the optimal move using XOR. How about changing the rule so that a player loses a game if he or she makes the XOR to 00?"

Bob: "It sounds much better now, but I suspect you know the surefire way to win."

Alice: "Do you wanna test me?"

This game is defined as follows.

  1. The game starts with NN heaps where the ii-th of them consists of a_ia\_i stones.
  2. A player takes any positive number of stones from any single one of the heaps in one move.
  3. Alice moves first. The two players alternately move.
  4. If the XOR sum, a_1a\_1 XOR a_2a\_2 XOR \cdots XOR a_Na\_N, of the numbers of remaining stones of these heaps becomes 00 as a result of a player's move, the player loses.

Your task is to find which player will win if they do the best move.

입력

The input consists of a single test case in the format below.

$N$
$a_{1}$
$\vdots$
$a_{N}$

The first line contains an integer NN which is the number of the heaps (1N1051 \le N \le 10^5). Each of the following NN lines gives the number of stones in each heap (1a_i1091 \le a\_i \le 10^9).

출력

Output the winner, Alice or Bob, when they do the best move.

힌트

In the first example, the XOR sum is 0 in the initial state, but the game is going because nobody moves yet. First Alice takes a stone and the XOR sum becomes 1, then Bob takes the last stone and the XOR sum becomes 0. Therefore, Alice will win, and Bob will lose.