Checker's Check

Checkers is played on an 8x8 board using only the 32 dark squares. Two players, Red and White, each control up to 12 pieces. The dark squares are numbered 1-32, row by row from the top of the board to the bottom, and left to right within each row:

   1   2   3   4
 5   6   7   8
   9  10  11  12
13  14  15  16
  17  18  19  20
21  22  23  24
  25  26  27  28
29  30  31  32

A forward move advances a piece toward the opponent's side. White pieces move forward toward lower-numbered squares (upward); Red pieces move forward toward higher-numbered squares (downward). The rules of movement and capture are:

1. Players alternate moves.
2. A piece may move one square diagonally forward to an empty square.
3. A piece may jump forward over an adjacent opposing piece when the square immediately beyond it is empty; the jumped piece is captured (removed). If, after a jump, the jumping piece can jump again, it must continue - this is a multiple jump.
4. If any jump is available, the player must make a jump. When several jumps are possible the player may choose any of them - even a single jump instead of a longer multiple jump - but once a multiple jump is begun it must be carried on until no further jump is possible.
5. The far row on the opponent's side (squares 29-32 for Red, squares 1-4 for White) is the promotion row. A piece reaching it becomes a king and may thereafter move and capture both forward and backward. Promotion ends the move immediately: a piece cannot begin or continue a jump after being crowned until its next turn.
6. During one move a piece may be jumped at most once (this matters only for a king making a multiple jump).

A move is written as the list of squares the moving piece visits, joined by hyphens. For example, 22-18 is a simple White move; 14-23 is a Red jump that captures the White piece on square 18; and 22-31-24-15 is a multiple jump by a White king capturing the Red pieces on 26, 27 and 19.

You are given a position from a game in progress and a sequence of moves to apply from that position. Determine whether every move is legal.

The input contains several game instances. Each instance begins with two integers $r$ and $w$ - the number of Red and White pieces on the board ($1 \le r, w \le 12$). A line with $r = w = 0$ marks the end of the input.

The next line lists the $r$ squares holding Red pieces, and the following line lists the $w$ squares holding White pieces. A positive value $sq$ means a normal piece stands on square $sq$; a negative value $-sq$ means a king stands on square $sq$.

The next line contains an integer $m \ge 1$ followed by a single character (R or W) giving the number of moves and which side moves first. Each of the following $m$ lines contains one move in the hyphen-separated notation above (at most 13 squares per move).

Every listed position is legal (no two pieces share a square), and any piece already on its promotion row is a king.

For each instance, print All moves valid if every move is legal. Otherwise print Move n is invalid, where move 1 is the first move of the instance; if several moves are illegal, report only the first one.