0을 만들면 지는 님

시간 제한2초메모리 제한512 MB

요약

각 힙에서 돌을 하나 이상 제거한 뒤 전체 XOR이 0이 되면 그 선수가 지는 님 변형 게임에서 최적 플레이의 승자를 판정한다.

문제

Alice: "안녕, Bob! 님 게임이나 하자!"

Bob: "진심이야? 하기 싫어. 나는 이 게임에서 이기는 방법을 알고 있거든."

Alice: "맞아, XOR로 최적의 수를 계산하는 알고리즘이 있지. 그럼 규칙을 바꿔서, 자기 차례에 XOR을 $0$ 으로 만들면 지는 걸로 하면 어때?"

Bob: "훨씬 재밌겠네. 그런데 너도 필승법을 알고 있는 거 아니야?"

Alice: "해볼래?"

게임은 다음과 같이 정의된다.

게임은 $N$ 개의 더미로 시작하고, $i$ 번째 더미에는 $a\_i$ 개의 돌이 있다.
한 번의 수로 하나의 더미에서 양의 개수의 돌을 원하는 만큼 가져갈 수 있다.
Alice가 먼저 두고, 두 사람은 번갈아 가며 둔다.
어떤 수의 결과로 남은 돌 개수들의 XOR 합 $a\_1$ XOR $a\_2$ XOR $\cdots$ XOR $a\_N$ 이 $0$ 이 되면, 그 수를 둔 사람이 진다.

두 사람이 최선의 수를 둘 때 누가 이기는지 구하시오.

입력은 아래 형식의 단일 테스트 케이스로 주어진다.

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

첫째 줄에는 더미의 개수 $N$ 이 주어진다 ( $1 \le N \le 10^5$ ). 다음 $N$ 개의 줄에는 각 더미에 있는 돌의 개수가 주어진다 ( $1 \le a\_i \le 10^9$ ).

두 사람이 최선의 수를 둘 때 이기는 사람을 Alice 또는 Bob으로 출력한다.

첫 번째 예제에서 초기 상태의 XOR 합은 0이지만, 아직 아무도 두지 않았으므로 게임은 진행된다. 먼저 Alice가 돌 하나를 가져가 XOR 합이 1이 되고, 이어서 Bob이 마지막 돌을 가져가 XOR 합이 0이 된다. 따라서 Alice가 이기고 Bob이 진다.