Battle Sheep

Battle Sheep is a game for two players, and the rules go like this.

Each player has an $N \times N$ grid and places four ships on it. The ships never overlap, and every ship is parallel to one of the two axes. Each player places exactly one of each of these ships:

The players call out cells in turn. If the cell player A calls is covered by a ship on player B's grid, player B announces a hit. Once every cell of that ship has been hit, player B announces that the ship sank, and player A calls again. If player A's call sinks no ship, the turn passes to player B. A player who has sunk all four of the opponent's ships wins, and the game stops there.

Alice and Bob got tired of calling out cells and making the announcements by hand, so they now write down where they placed their ships and the order in which they want to call cells. Neither of them calls the same cell twice. Bob is a gentleman and always lets Alice start.

Given both grids and both lists of planned calls, report which ships sank, in the order they sank, and who won.

The first line holds one integer $T$, the number of test cases.

Each test case begins with a line holding one integer $N$, the size of the grids.

The next $N$ lines hold Alice's grid, one line of $N$ characters each. Each character is ., 1, 2, 3 or 4. A . is an empty cell. A digit means the cell is covered by one of Alice's ships, and all cells holding the same digit belong to the same ship. The digit does not tell you the length of the ship.

The next $N$ lines hold Bob's grid in the same format.

The next $N^2$ lines hold Alice's planned calls. Each line holds two integers $R_i$ and $C_i$, the row and the column she calls on that move, if the game lasts that long.

The next $N^2$ lines hold Bob's planned calls, in the same format.

• $1 \le T \le 20$
• $4 \le N \le 10$
• $1 \le R_i, C_i \le N$
• Every ship is a straight run of equal characters parallel to one of the axes.
• Neither player calls the same cell twice, so each list of calls covers every cell of the grid exactly once.

For each test case, print one line for every ship that sank, in the order the ships sank:

PlayerX sank PlayerY's ShipName

PlayerX is the player who made the call, PlayerY is the owner of the ship, and ShipName is the name of the ship from the table. Both player names are written as Alice and Bob.

After those lines, print one more line holding the name of the winner.