Sokoban

Sokoban is a game created in Japan in 1982; its name means "warehouse keeper" in Japanese. The player moves a character to push every box onto a goal, and wins once all boxes rest on goals. The number of boxes always equals the number of goals.

The player can order the character to move in one of four directions — up, down, left, or right — under these rules:

• If the cell in the ordered direction is empty (neither a box nor a wall), the character moves onto it.
• If the cell in the ordered direction holds a box, the box is pushed. This is only allowed when the cell the box would move into is also empty.
• If the ordered direction is a wall, or holds a box whose destination cell is occupied by another box or a wall, the character does not move.

The game ends the moment every box sits on a goal. Any keys entered after the game ends are ignored.

Deciding whether a Sokoban puzzle is solvable is very hard (it is NP-hard and PSPACE-complete), so here you only need to simulate the given key presses faithfully.

Each cell of the board is represented by one of the following characters:

Given the keys the player presses in order, write a program that reports how the game unfolds. The first example below illustrates the rules.

The input consists of several test cases.

The first line of each test case contains the number of rows $R$ and columns $C$ of the board. ($4 \le R \le 15$, $4 \le C \le 15$) The next $R$ lines describe the current board; every line consists of exactly $C$ characters. The following line lists the keys the player pressed, in order, with length at most 50. Up, down, left, and right are written as U, D, L, and R.

The last line of the input is 0 0.

Every board given as input contains exactly one character, and the number of boxes equals the number of goals. At least one box is not on a goal, and every cell on the outer border of the board is a wall.

For each game, first print Game k: complete or Game k: incomplete, where $k$ is the game number starting from 1 and increasing in order. Print complete if every box was moved onto a goal and the game finished, and incomplete otherwise. Then print the final state of the game on $R$ lines.