分数: 500 点
问题陈述
有 N 成堆的石头,以及 i第一堆 (1\le i\le N) 有 A_i 石头。
Alice 和 Bob 将使用这些桩玩以下游戏:
- 从 Alice 开始,两名玩家轮流轮流。
- 在每一回合中,玩家选择一堆非空的石子,并从该堆中移走一颗或多颗石子。然而,玩家不能采取改变按位的动作 \mathrm{OR} 所有堆石子的数量。
无法先行动的玩家失败。
确定当两名玩家都发挥最佳状态时哪个玩家获胜。
你被给予 T 测试用例;解决它们中的每一个。
什么是按位 \mathrm{OR}?
按位 \mathrm{OR} 非负整数的 A 和 B, A\ \mathrm{OR}\ B,定义如下:
- 当 A\ \mathrm{OR}\ B 以二进制形式写入,其中的数字 2^k 地点(k \geq 0) 是 1 如果至少有一位数字 2^k 地点 A 和 B 写成二进制是 1,和 0 否则。
一般来说,按位 \mathrm{OR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\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 如果当两个玩家都发挥最佳状态时爱丽丝获胜,并且 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
考虑第一个测试用例。
最初,按位 所有堆石子的数量 \mathrm{OR} 是 3\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=7.
Alice可以采取的动作如下:
- 从第一堆中取出两块石头。
- 从第二堆中取出一颗或多颗石头。
- 从第三堆中取出一颗或多颗石头。
例如,如果爱丽丝从第一堆石头中取出一块石头,则按位 所有堆的石子数量的 \mathrm{OR} 变为 2\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=6。因此,爱丽丝不能采取从第一堆石头中取出一块石头的举动。
如果爱丽丝从第三堆中取出六颗石子,鲍勃在下一回合将无法进行任何移动。因此,当双方都发挥最佳状态时,Alice 获胜。