Black and White Stone Game

Many thanks to Clive Fraser for creating this elaborate puzzle!

Ann and Bob enjoy designing new two-player games using piles of stones. They have a large number of stones, in two different colours, black and white. Their latest game begins with a number of piles of stones. Each pile can contain any number of stones but all of the stones in a pile must have the same colour. Players take it in turns to remove one or more stones from the game. The player who removes the last stone is the winner.

The rules for removing stones are slightly different for the two players.

On her move, Ann can remove any single white stone (leaving the remainder of the pile, if any) or she can completely remove any single pile of black stones.

On his move, Bob can remove any single black stone (leaving the remainder of the pile, if any) or he can completely remove any single pile of white stones.

As with many games of this type, if the players play optimally then the eventual winner can be determined by analysis of the starting position. This means that for any starting position there is a winning strategy for one of the two players. This assumes optimal play from both players.

Consider a very small example game which has 3 piles of white stones containing 1, 1 and 2 stones respectively. It also has 2 piles of black stones containing 1 and 3 stones respectively. With such a small example it is easy to explore every possible sequence of moves. It should be easy to confirm that, with optimal play, Ann wins the game. In fact Ann wins the game whether she plays first or second.

Analysis of a number of games shows that there are four possibilities: Either Ann or Bob can win, whoever goes first. The other possibilities are that the first player (whoever that is) will win the game, or that the second player will win the game. We will use single characters to label each of these possibilities. They are summarised in the table below:

A       Ann wins, whoever goes first
B       Bob wins, whoever goes first
1       The first player wins
2       The second player wins

You will be given a number of starting positions for the game and are asked to determine, assuming optimal play, which player wins. Give your answer as one of the four characters from the table above.

Input/Output description: The first line of the input data will consist of a single integer G for the number of games. The data for each game is on 3 separate lines. The first line contains two integers, W and B for the number of piles of white and black stones respectively. The second line contains W integers for the number of stones in each of the white piles. The third line contains B integers for the number of stones in each of the black piles. For each game, find the winner, assuming optimal play. Combine all of your answers into a single string, separated by spaces.

Example:

input:
4
3 2
1 1 2
1 3
16 17
1 2 20 27 27 30 37 40 40 41 48 54 66 69 80 87
16 17 18 22 24 27 29 32 34 36 43 44 50 61 61 70 86
18 18
1 1 1 14 18 22 23 30 48 50 61 69 69 73 74 85 87 98
2 6 12 23 24 25 30 34 42 47 48 65 68 69 69 85 86 89
18 17
10 12 19 25 36 36 44 45 46 47 47 47 55 61 66 72 82 87
3 8 21 23 36 41 42 45 46 61 63 64 72 73 74 79 83

answer:
A 1 2 B