148 - The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - G
Alice and Bob are playing yet another game of stones. The rules of this game are as follow:
Alice is always the first to make a move. Do you know who will win the game if they both play optimally?
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 105), indicating the number of piles.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), indicating the number of stones in each pile.
The third line of each test case contains n integers b1, b2, ..., bn (0 ≤ bi ≤ 2), indicating the special constraint of each pile.
It is guaranteed that the sum of n over all test cases does not exceed 106.
We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
For each test case, output "Alice" (without the quotes) if Alice will win the game. Otherwise, output "Bob" (without the quotes).
3 2 4 1 1 0 1 3 2 1 1 2
Alice Bob Bob
For the first test case, Alice can remove 3 stones from the first pile, and then she will win the game.
For the second test case, as Alice can only remove some even number of stones, she is unable to remove all the stones in the first move. So Bob can remove all the remaining stones in his move and win the game.
For the third test case, Alice is unable to remove any number of stones at the beginning of the game, so Bob wins.