Corgi Chess Interference

Players A and B play a game on an \(n \times n\) chessboard by placing a corgi on an unoccupied cell. Player A moves first followed by player B. When a corgi is placed at \((x, y)\), the four diagonal neighbors \((x-1, y-1)\), \((x-1, y+1)\), \((x+1, y-1)\), and \((x+1, y+1)\) become controlled by that corgi and are no longer available for future moves. The player who is unable to place a corgi loses the game.

To spoil the game, player C intervenes. After A and B have placed a total of \(x_i\) corgis, player C expands the current \(w \times w\) board (with \(w = n\) initially) to a \((w+2) \times (w+2)\) board by adding a border around it. This interference happens exactly \(q\) times in the game. Note that if A and B are unable to make a move on the current board, they will immediately proceed to the next interference (if any).

Both players know about C's interference and play optimally. Under optimal play the final outcome is determined solely by the maximum number of placements available on the board after all \(q\) interference events. Since the interference always expands the board by adding a border, at the end the board will be of size \(n+2q\). It can be shown that the maximum number of placements (using a checkerboard pattern) is given by \[ f(w) = \begin{cases} \frac{w^2}{2} & \text{if } w^2 \text{ is even},\\[6pt] \frac{w^2+1}{2} & \text{if } w^2 \text{ is odd}. \end{cases} \] Thus, if \(f(n+2q)\) is odd, player A wins; otherwise, player B wins.

Your task is to decide the winner for each of the \(T\) games. If player A wins, output A won; otherwise, output B won.

inputFormat

The first line contains an integer \(T\) representing the number of games.

Each game is described as follows:

• The first line contains two integers \(n\) and \(q\), where \(n\) is the initial board size and \(q\) is the number of interference events.
• If \(q > 0\), the next line contains \(q\) integers \(x_1, x_2, \ldots, x_q\) (space separated) which indicate the move counts at which player C performs the interference. (These values are generated randomly and do not affect the final outcome under optimal play.)

outputFormat

For each game, output a single line: A won if player A wins; otherwise, output B won.

sample

3
1 0

2 0

3 1
5

A won
B won
A won