410230: GYM103987 F Do Not Play Nim

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".

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$$$.

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!".

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.

3
1
10
2
1 1
6
1 1 4 5 1 4

Alice
Bob
Alice

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!