Janken Tactics

Janken, also known as rock-paper-scissors, is a popular children's game. In the grand tradition of game development, one company has decided to put a strategic twist on the classic. The resulting war simulation, Janken Tactics, is in development, and you have been hired as a programmer to work on the move-validation code.

Janken Tactics takes place on a hex-hex grid with five cells on each side. Each cell has a terrain type that helps or hinders movement. Normally, moving into an adjacent cell costs one movement point, but the destination cell's terrain may make it cost more:

• Moving into a Field costs no extra points (1 total);
• Moving into Woods costs one extra point (2 total);
• Moving into Hills costs two extra points (3 total);
• Moving into Mountains costs three extra points (4 total);
• no unit may move into an Underwater cell (units never start on one either).

The grid layout and coordinate system are shown below:

      4 5 6 7 8 9
     3 \ \ \ \ \ \
    2 \ \ * * * * * -- A
   1 \ \ * * * * * * -- B
    \ \ * * * * * * * -- C
     \ * * * * * * * * -- D
      * * * * * * * * * -- E
       * * * * * * * * -- F
        * * * * * * * -- G
         * * * * * * -- H
          * * * * * -- I

A cell's coordinate is its row letter (A-I) followed by its column number. The center cell of the top row is A7, and the rightmost vertex of the grid is E9. Adjacent cells are the two in the same row (immediately left and right) and the four along the diagonals. For example, the cells adjacent to E5 are D5, D6, E4, E6, F4, and F5.

Mirroring Janken, there are three unit types: the Guardian (rock), the Mage (paper), and the Swordsman (scissors). Every unit has 10 movement points to spend per move. Their strengths and weaknesses are:

• Guardians defeat Swordsmen but are defeated by Mages;
• Mages defeat Guardians but are defeated by Swordsmen;
• Swordsmen defeat Mages but are defeated by Guardians.

You are not writing the combat code, but these relationships still matter for movement. During a move, a unit cannot pass over an enemy unit, and cannot pass within one cell of an enemy unit that is strong against it (a Guardian cannot pass within one cell of a Mage, a Mage cannot pass within one cell of a Swordsman, and a Swordsman cannot pass within one cell of a Guardian). A unit may, however, end its move on a cell adjacent to (but not the same as) any enemy unit, and it may pass through cells occupied by allied units of any type. The destination cell must be empty (no allied or enemy unit). There is never more than one unit on a cell between moves.

Your task is to decide whether a given unit can make a requested move, and if so, how many movement points remain afterward. Choose the path that maximizes the leftover movement points. A move is invalid if:

• the starting cell has no unit;
• the destination cell is already occupied;
• reaching the destination would cost more movement points than the unit has;
• or the destination cannot be reached without passing over Underwater cells or enemy units, or passing next to an enemy unit that is strong against the moving unit.

You process a sequence of moves. If a move is invalid, the unit (if any) stays on its starting cell. The moves in a data set happen one after another; do not reset the grid between moves.

The input begins with a line containing a single integer $n$, the number of data sets. Each data set is given as follows.

First come nine lines describing the grid's terrain, one line per row A through I, using F for Field, W for Woods, H for Hills, M for Mountains, and U for Underwater. The cells on each line are listed left to right in increasing column order.

The next line contains two integers $M$ $P$ ($1 \le M, P \le 10$), the number of units on each side. The following $M$ lines each contain a type $T$ and a location $L$, where $T$ is G (Guardian), M (Mage), or S (Swordsman) and $L$ is the unit's starting cell in the coordinate format above. The next $P$ lines describe the second side in the same way.

The next line contains an integer $V$ ($1 \le V \le 100$), the number of moves to test. Each of the following $V$ lines contains two coordinates $S$ $E$: the starting cell (and therefore the unit) and the attempted destination cell. Moves may belong to either side.

For each data set, first print Game #X, where $X$ is the data set number starting from 1. Then, for each move in the data set, print one line:

• Move #N (S -> E): Successful (M points left) if the move succeeds, or
• Move #N (S -> E): Unsuccessful if it fails.

Here $N$ is the move number (starting at 1), $S$ and $E$ are the starting and destination coordinates, and $M$ is the number of movement points left after the move.