/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
石の山が N 個あり、 i 番目 (1\le i\le N) の山には A_i 個の石が積まれています。
Alice と Bob がこれらの山を使って以下のようなゲームを行います。
- Alice から始めて両者は交互に手番をプレイする。
- 各手番では、プレイヤーは空でない山を一つ選び、その山から 1 個以上好きな個数の石を取り除く。ただし、石を取り除く前後で「全ての山の石の個数をビット単位 \mathrm{OR} 演算することで得られる値」が変わるような行動を取ることはできない。
先に手番をプレイできなくなったプレイヤーの負けです。
両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
ビット単位 \mathrm{OR} 演算とは
非負整数 A, B のビット単位 \mathrm{OR}、A\ \mathrm{OR}\ B は以下のように定義されます。
- A\ \mathrm{OR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち少なくとも片方が 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{OR} は (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1\le T\le 10^5
- 2\le N \le 2\times 10^5
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 1\le A_i \le 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N A_1 A_2 \ldots A_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、両者が最善を尽くしたとき Alice が勝つならば Alice を、Bob が勝つならば Bob を出力せよ。
入力例 1
4 3 3 4 6 3 7 7 7 3 9 3 5 10 1 9 1 3 7 9 10 9 7 3
出力例 1
Alice Bob Bob Alice
1 つ目のテストケースについて考えます。
はじめ、全ての山の石の個数をビット単位 \mathrm{OR} 演算することで得られる値は 3\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=7 です。
Alice がプレイすることのできる手番は以下の通りです：
- 1 番目の山から 2 個石を取り除く。
- 2 番目の山から 1 個以上好きな個数の石を取り除く。
- 3 番目の山から 1 個以上好きな個数の石を取り除く。
例えば 1 番目の山から 1 個石を取り除いた場合、全ての山の石の個数をビット単位 \mathrm{OR} 演算することで得られる値は 2\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=6 となります。したがって、 Alice は 1 番目の山から 1 個石を取り除く行動を取ることはできません。
Alice が 3 番目の山から 6 個石を取り除いた場合、 Bob はその次の手番がプレイできなくなります。したがって、両者が最善を尽くしたときの勝者は Alice です。
Score : 500 points
Problem Statement
There are N piles of stones, and the i-th pile (1\le i\le N) has A_i stones.
Alice and Bob will play the following game using these piles:
- Starting with Alice, the two players take turns alternately.
- In each turn, the player chooses one non-empty pile and removes one or more stones from that pile. However, the player cannot make a move that changes the bitwise \mathrm{OR} of the numbers of stones of all piles.
The player who cannot make a move first loses.
Determine which player wins when both players play optimally.
You are given T test cases; solve each of them.
What is bitwise \mathrm{OR}?
The bitwise \mathrm{OR} of non-negative integers A and B, A\ \mathrm{OR}\ B, is defined as follows:
- When A\ \mathrm{OR}\ B is written in binary, the digit in the 2^k place (k \geq 0) is 1 if at least one of the digits in the 2^k place of A and B written in binary is 1, and 0 otherwise.
In general, the bitwise \mathrm{OR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k), and it can be proved that this is independent of the order of p_1, p_2, p_3, \dots p_k.
Constraints
- 1\le T\le 10^5
- 2\le N \le 2\times 10^5
- The sum of N over all test cases is at most 2\times 10^5.
- 1\le A_i \le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A_1 A_2 \ldots A_N
Output
Output the answers for each test case in order, separated by newlines.
For each test case, print Alice if Alice wins when both players play optimally, and Bob if Bob wins.
Sample Input 1
4 3 3 4 6 3 7 7 7 3 9 3 5 10 1 9 1 3 7 9 10 9 7 3
Sample Output 1
Alice Bob Bob Alice
Consider the first test case.
Initially, the bitwise \mathrm{OR} of the numbers of stones of all piles is 3\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=7.
The moves Alice can make are as follows:
- Remove two stones from the first pile.
- Remove one or more stones from the second pile.
- Remove one or more stones from the third pile.
For example, if Alice removes one stone from the first pile, the bitwise \mathrm{OR} of the numbers of stones of all piles becomes 2\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=6. Therefore, Alice cannot make the move of removing one stone from the first pile.
If Alice removes six stones from the third pile, Bob cannot make any move in the next turn. Therefore, the winner when both players play optimally is Alice.