Xiang Hex is Chinese Chess played upon an elongated hexagonal field, consisting of nine files with the outer ones being seven cells and the center being eleven. The "palace" consists of seven cells, the first three cells of the center file and the first two cells which flank. The "river" is denoted by fourth cell of the first and ninth file, the fifth cell of the third and seventh file and the sixth cell of the center file. The player's side of the field consists of the cells before the "river".

If you know how to play Chess, the rules of Xiang Hex will be familiar. The general idea is the same. Each player controls an army (red or black) of pieces, moves one piece at a time, and tries to get the opponent's royal piece.

You can see the "palace" and the "river" below: ("r" is the "river", "P" is the "palace" of red army, and "p" is the "palace" of black army)

Each file was marked from the left to the right with an uppercase character A, B ... I, and the location of a hexagonal can be expressed by the character of the file and the number of hexagonal under it in the same file (No space between the character and the number).

There are seven kinds of pieces in Xiang Hex:

1. SOLDIER(S) step one forward orthogonal before entering the "river". Upon and after entering the "river" step one forward, right forward or left forward orthogonal, or right or left diagonal.
2. HORSE(H) step one vacant orthogonal then one diagonal in the same direction.
3. CHARIOT(C) slide orthogonal.
4. CANNON(A) slide orthogonal through vacant cells, may leap any one piece to capture an enemy.
5. ELEPHANT(E) step two diagonal and never cross the "river".
6. MANDARIN(M) step diagonal and never leave the "palace"
7. GENERAL(G) step orthogonal and never leave the "palace". Not permitted be on an empty file with the opposing GENERAL.

And this is the setup of Xiang Hex: (Lowercase pieces belong to black army and uppercase pieces belong to red army)

The game is won by checkmating the opposing GENERAL. A player loses if stalemate or repetition of position. If both players have no pieces which can cross the "river", the game is drawn.

Recently, the Association of Chess Men (ACM) wants to hold a competition of Xiang Hex. However, they don't know how to display the current board in real-time during the games. Now they ask you for help.

There are several test cases in the input. The first line of each case contains an integer n, the number of pieces on the board. The following n lines, each line contains the location of the pieces and a character indicates the type of the pieces. The input is ended by n = 0.

Just display the board as the sample. Extra space at the end of line is not allowed.