Link and Pop -- the Block Game

Robert recently found a new game on the Internet, the newest version of 'Link and Pop'. The rules are very simple. Initially, a board of size $n \times m$ is filled with $n \times m$ blocks, and each block has a single symbol on it. Your task is to find a pair of blocks bearing the same symbol that can be joined by a line made of at most three straight horizontal or vertical segments. The line may not pass through any other block on the board (Fig. 1 shows some examples of valid links; note that some blocks have already been removed from the board).

Fig. 1

When such a pair is found, the two blocks are popped (removed) together. After that, some blocks may move to new positions according to the rules described below. You then look for the next pair. The game continues until no blocks remain on the board, or until no such pair can be found.

Blocks move according to the following rules. First, every block has a fixed moving attribute, one of 'up', 'down', 'left', 'right', or 'stand still'. After a pair is removed, the blocks are checked one by one to see whether each can move in the direction of its moving attribute. Blocks in the top row are checked first, and within the same row the leftmost blocks are checked first. If the adjacent cell in the direction of the block's attribute is empty, the block moves there immediately. No block may move beyond the boundary of the board. A block with the 'stand still' attribute always keeps its position. Checking every block once is called a turn of checking; when a turn ends, another turn begins. This repeats until no block can move any more. Within a single turn, each block is checked and possibly moved only once, and a block that has already moved this turn must not be checked or moved again at its new position.

Robert found the game very interesting. However, after playing for a while, he noticed that when the board is fairly large, finding a pair becomes very hard, and he often reaches 'Game Over' because no more blocks can be popped. Robert felt it was not his fault that not all blocks could be popped; it is simply that when the blocks are placed randomly at the start, there is a good chance the game cannot be finished. Proving this by playing many times would be very time-consuming, so Robert asks you to write a program that simulates his behavior and reports whether the game can be finished.

To make such a program possible, Robert summarizes his rule for choosing pairs as follows. First, if a pair that can be joined by one straight segment exists, it must be found and popped first, because such pairs are easy to find. Otherwise, pairs that can be joined by two straight segments must be found and popped. Finally, if neither kind exists, pairs that can be joined by three straight segments must be found and popped. If more than one pair can be joined with the same number of straight segments, the pair containing the block positioned in the topmost row (or leftmost, if two blocks are in the same row) is chosen first. If this still does not break the tie (several pairs may share the same topmost-leftmost block), the other block of those pairs is compared by the same rule. Fig. 2 shows a trace of a mini game of 'Link and Pop' that follows the rules above.

Fig. 2

The input contains no more than 30 test cases. The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 30$), the size of the board. This line is followed by $n$ lines, each containing $m$ strings separated by single spaces. Each string represents one block in the initial configuration and always consists of two capital letters. The first letter is the block's symbol. The second letter is always one of 'U', 'D', 'L', 'R', 'S', giving the block's moving attribute: up, down, left, right, and stand still respectively. There are no blank lines between test cases. The input ends with a line containing two zeros: '0 0'.

For each test case, first output the test case number in the form Case k. After that line, output the final configuration of the board as $n$ lines, each containing $m$ characters. If there is a block at a position, output the block's symbol; if there is no block, output a period ('.') instead. Do not output blank lines between test cases.