The Tower

Time Limit : 2 sec, Memory Limit : 65536 KB
Japanese version is here

Problem L: The Tower

Your task is to write a program that reads some lines of command for the following game and simulates operations until the player reaches the game over. We call following 2-dimensional grid of m by n characters Tower. The objective of this game is to move blocks in the tower to climb to a goal block. In the following grid, the bottom line is the first row and the top one is the n-th row. The leftmost column is the first column and the rightmost one is the m-th column.

.................... (n=13 th row)
.....#.....G........
....##.....##.....##
...####...IIII...###
..####.....##.....##
...####B..####....##
....###....#33##..##
.....####...#33#3.##
.##CCCC#####2##.####
..#####..###.#...###
...###....###.....#1
....####..##.......#
S..###..#.####.....# (1st row)

Explanation of cell marks:

  • '#' : Normal block
    Normal block.
  • 'I' : Ice block
    Block made of the ice. This has different features from the normal one.
  • 'G' : Goal block
    If the player climbs to this, game is over and clear.
  • 'C' : Fixed block
    The player can not move this directly.
  • 'B' : Different dimensional block
    If the player climbs to this, game is over and lose.
  • '.' : Space
    Empty place.
  • '3' : Fragile block(3)
    A fragile block of count 3.
  • '2' : Fragile block(2)
    A fragile block of count 2.
  • '1' : Fragile block(1)
    A fragile block of count 1. If the count is zero, this block will be broken and become a space.
  • 'S' : Player
    The player.

Explanation of relative positions:

123
4S5
678

In the following description, assume that left up is the position of 1, up(over S) is 2, right up is 3, left is 4, right is 5, left down is 6, down(under S) is 7, right down is 8 for S.

Movements of the player
The player must not go out of the tower. The outside of the tower is considered as space cells.

  • Move
    The player can move everywhere in the current row as long as some of the following conditions are satisfied.
    • The player is in the first row and the target cell is a space.
    • There are blocks under the route connecting the current cell and the target cell (horizontal segment) and the target cell is a space. It is OK that some blocks in the horizontal segment. And the case that some of blocks under the segment are different dimensional ones, it is also OK.
  • Climb
    If the player at the row below the n-th row (from 1st to n-1 th row) and there is a block in the right(left) and both of a cell over the player (up cell) and a right up(left up) cell are space, the player can move to the right up(left up) cell.
  • Get down
    If the player at the row above the 1st row (from 2nd to n-th row), he can get down to right(left) down. If the direction for getting down is right(left) and if there is no blocks in the right down (left down) cell and the right (left) cell, the player can move to the right down (left down) cell.
  • Push
    If there is a block or continuous blocks in the right or left of the player, he can push the blocks to the direction one cell. Here, blocks are "continuous" if there are two or more blocks and no space exist between them. However, if there is a fixed block in pushing blocks, the player can not push them. Pushed blocks will not stop the end of the row of the tower (1st and mth column). If the pushed blocks go out of the tower, this will be vanished.
    In the result of pushing, a block moved over the ice block continues to move to the pushed direction as long as there is a space in the progress direction, there is an ice block under the block and the pushed block is not vanished.
    If the pushed block is an ice block, this continues to move to the pushed direction as long as there is a block under the ice block, there is a space in the progress direction and the pushed ice block is not vanished. However, for an ice block in the first row, the below the block do not have to be a space. And here, if the player pushes continuous blocks, pushing movements begin from the most distant block to a nearest block. Here, the distance is manhattan distance at the gird.
  • Pull
    If there is a block in the right(left) of the player and the left(right) cell is space, the player can pull the block. However, if the pulling block is fixed one, he can not pull this. If the player pulls block, the player will move one cell to the direction of pulling.

Automated operations after the player operation:
Automated operations occur in the following order. This repeats in this order as long as the cells of the tower are changed by this operations. After this operations, the player can do the next operation.

  • Countdown of fragile blocks
    If the player over a fragile block moved to somewhere else, that fragile block's count will decrease by one. However, this count does not change if the player over the fragile block is moved to somewhere else by the automated operations.
  • Erasing blocks
    A block over an different dimensional block will be vanished.
  • Falling of the player
    If there is no block under the player, the player continues to fall as long as satisfying this condition or come to 1st row.
  • Falling of blocks
    If there is no block under a block and left down and right down of a certain block, the block in the row over the 1st row (from 2nd to n-th row) continues to fall as long as satisfying this condition. Falling of blocks begins from lower blocks of the tower and then lefter blocks.

Conditions for game over:
After the movement of the player or the automated operations, the game is over when the one of next conditions is satisfied. These conditions are judged in the following order. Note that, the condition (E) should not be judged after the movement of the player.

  • (A) The player is over the goal block.
  • (B) The player is over the different dimensional block.
  • (C) The player and a block is in the same cell.
  • (D) The goal block is moved from its initial position.
  • (E) There is no next commands.

Finally, show some examples.
Documents of commands will be give in the description of Input.

Example table
Movement or
Automated operation
BeforeAfterCommand
Move.#S
###
S#.
###
MOVETO 1
Climb...
3S#
S..
3.#
CLIMB LEFT
Get downS..
3.#
...
2S#
GETDOWN RIGHT
Push.#S#####..
###II.I.I.
.#S.####.#
###II.I.I.
PUSH RIGHT
Push.#SI...
###.###
.#S....
###.###
PUSH RIGHT
Push.#...S#
###.###
.....S.
###.###
PUSH RIGHT
Pull..S#####..
###.#.#.#.
.S#.####..
###.#.#.#.
PULL LEFT
Falling of the player.#S#
.#.#
.#.#
.#.#
.#.#
.#.#
.#.#
.#S#
-
Falling of blocks.###.
#...#
#...#
#...#
.#.#
.#.#.
#...#
#...#
#.#.#
.#.#
-

Input

Input consists of multiple datasets.
A dataset is given in the following format.

n m
Dn,1 Dn,2 ... Dn,m
Dn-1,1 Dn-1,2 ... Dn-1,m
...
D1,1 D1,2 ... D1,m
T
Command1
Command2
...
CommandT

Here, m, n is the width and height of the tower. Di,j(1≤in and 1≤jm) is a mark of the cell. The explanation of marks described above. Commandk(1≤kT) is the k-th player operation (movement). This is a string and one of following strings.

"MOVETO s"  means move to s-th column cell in the same row.
"PUSH RIGHT" means push right block(s).
"PUSH LEFT" means push left block(s).
"PULL RIGHT" means pull the left block to right.
"PULL LEFT" means pull the right block to left.
"GETDOWN RIGHT" means get down to right down.
"GETDOWN LEFT" means get down to left down.
"CLIMB RIGHT" means climb to the right block.
"CLIMB LEFT" means climb to the left block.

Some of commands are invalid. You must ignore these commands. And after game is over, the command input may continue in case. In this case, you must also ignore following commands. m=n=0 shows the end of input.

Constraints

3≤m≤50
3≤n≤50
Characters 'S' and 'G' will appear exactly once in the tower description.

Output

Each dataset, output a string that represents the result of the game in the following format.

Result

Here, Result is a string and one of the following strings (quotes for clarity).

  • "Game Over : Cleared" (A)
  • "Game Over : Death by Hole" (B)
  • "Game Over : Death by Block" (C)
  • "Game Over : Death by Walking Goal" (D)
  • "Game Over : Gave Up" (E)

Sample Input

8 8
........
........
....###.
...#.#.G
S#B...##
#ICII.I#
#..#.#.#
.#..#.#.
7
PUSH RIGHT
MOVETO 2
CLIMB RIGHT
CLIMB RIGHT
GETDOWN RIGHT
CLIMB RIGHT
GETDOWN RIGHT
8 8
........
........
........
...G....
S#B.....
#ICIIIII
#..#.#.#
.#..#.#.
4
PUSH RIGHT
MOVETO 2
CLIMB RIGHT
CLIMB RIGHT
8 8
........
....#.#.
.....#.G
...#..#.
S#B....#
#ICIII.#
#..#.#.#
.#..#.#.
8
PUSH RIGHT
MOVETO 2
CLIMB RIGHT
CLIMB RIGHT
CLIMB RIGHT
GETDOWN RIGHT
CLIMB RIGHT
GETDOWN RIGHT
0 0

Sample Output

Game Over : Death by Hole
Game Over : Cleared
Game Over : Death by Walking Goal

Source: University of Aizu Programming Contest , Aizu-Wakamatsu, Japan, 2011-06-05
Problem Setter:  Yohei Mori