410230: GYM103987 F Do Not Play Nim

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Do Not Play Nimtime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Yjmeimei likes game theory, but she is not smart enough to solve any related problem.

Now Zygege gives her a new problem.

There are $$$n$$$ piles of stones. Alice and Bob take turns removing them. On Alice's turn, she can remove an arbitrary number of stones (at least one) from a single pile. On Bob's turn, he can remove some stones from a single pile, and the number of stones he chooses should not be less than the number of stones Alice has removed in total. Alice plays first, and the player who cannot make a move loses.

Now Yjmeimei needs to figure out who will win the game if both Alice and Bob play the game optimally. Of course it is still too hard for her, so she asks you for help.

Since the problem is a bit like Nim, Yjmeimei names it "Do Not Play Nim".

Input

The input contains several test cases.

The first line of the input contains an integer $$$T\ (1\le T\le 10)$$$, the number of test cases.

For each test case, the first line contains an integer $$$n\ (1\le n\le 2\cdot 10^5)$$$ indicating the number of piles of stones. The second line of contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i\ (1\le a_i\le 10^9)$$$ represents the number of stones in the $$$i$$$-th pile.

It is guaranteed that the sum of $$$n$$$ in all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print "Alice" or "Bob" (without quotes) in one line indicating the winner. If the result is not deterministic, print "Awson is God!".

Scoring

The problem contains several subtasks. You can get the corresponding score for each passed test case.

  • Subtask 1 ($$$20$$$ points): $$$n\le 2$$$.
  • Subtask 2 ($$$80$$$ points): no additional constraints.
ExampleInput
3
1
10
2
1 1
6
1 1 4 5 1 4
Output
Alice
Bob
Alice
Note

In the first case, Alice can take $$$6$$$ stones, and it will be impossible for Bob to take no less than $$$6$$$ stones, so Alice wins.

In the second case, Alice will remove the first pile, and Bob will remove the second pile. Alice cannot move after that for all stones are removed, so Bob wins.

The third case is too smelly for Yjmeimei to elaborate on!

加入题单

上一题 下一题 算法标签: