Chess P44731

Write a program that analyses several chess positions, very simplified. In particular, the black player only has his king, while the white player only has rooks, bishops and queens. Remember that kings can only do horizontal, vertical and diagonal movements, and just one step. The other pieces can move more than one square at a time: the rooks, horizontally and vertically; the bishops, diagonally; the queens, horizontally, vertically, and diagonally.

Your program must determine all the positions where the black king can move to, that is, all the neighbouring positions of the black king that are not threatened by any white piece. (If the king has an enemy piece around him and this one is not defended, the king can move to this position “killing” the enemy piece.) If the black king does not have any valid movement, print “checkmate” if the position of the king is threatened, and “stalemate” if it is not.

Input

Input starts with the number of test boards n, followed by n boards. Each board consists of the position of the black king, followed by the number of white pieces m (between 0 and 63), followed by m pieces, each one of them defined by its type (R, B or Q) and its position. The positions are defined by a column (a letter between a and h) and a row (a number between 1 and 8). All the pieces of a board are in different positions.

Output

For each board, print its number starting at 1, followed by all the positions where the black king can move to, in alphabetical order. If there is no possible movement, print “checkmate” or “stalemate” depending on the case.

Scoring

• Test1:  ‍20 Points ‍

  Solving cases like those in sample 1, where the white player only has rooks.

• Test2:  ‍20 Points ‍

  Solving cases like those in sample 2, where the white player only has bishops.

• Test3:  ‍20 Points ‍

  Solving cases like those in sample 3, where the white player only has queens.

• Test4:  ‍40 Points ‍

  Solving cases like those in sample 4, where the white player has pieces of the three kinds.