체커 규칙 검사기

문제

체커는 8x8 판의 어두운 칸 32개만 사용해 진행합니다. 두 사람, Red(빨강)와 White(하양)가 각각 최대 12개의 말을 움직입니다. 어두운 칸에는 판의 위에서 아래로, 각 줄 안에서는 왼쪽에서 오른쪽 순서로 1-32번이 매겨져 있습니다.

   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

전진 이동이란 말이 상대 진영 쪽으로 나아가는 이동을 말합니다. White의 말은 번호가 작아지는 방향(위쪽)으로 전진하고, Red의 말은 번호가 커지는 방향(아래쪽)으로 전진합니다. 이동과 잡기 규칙은 다음과 같습니다.

두 사람이 번갈아 한 번씩 둡니다.
말은 대각선 방향으로 한 칸 전진해 빈 칸으로 이동할 수 있습니다.
상대 말이 바로 옆 대각선 칸에 있고 그 너머 칸이 비어 있으면, 그 말을 뛰어넘어 전진할 수 있습니다. 뛰어넘은 상대 말은 잡혀서 판에서 제거됩니다. 뛰어넘은 뒤 같은 말이 또 뛰어넘을 수 있다면 계속해서 뛰어넘어야 하며, 이를 연속 점프라고 합니다.
뛰어넘기가 하나라도 가능하면 반드시 뛰어넘어야 합니다. 여러 뛰어넘기가 가능할 때는 그중 어느 것이든 골라도 되고, 더 긴 연속 점프 대신 한 번짜리 점프를 골라도 됩니다. 다만 연속 점프를 시작했다면 더 이상 뛰어넘을 수 없을 때까지 끝까지 이어가야 합니다.
상대 진영의 맨 끝 줄(Red는 29-32번 칸, White는 1-4번 칸)이 승격 줄입니다. 이 줄에 도달한 말은 킹이 되어 이후로는 전진과 후진 양쪽으로 이동하고 잡을 수 있습니다. 승격하면 그 즉시 이동이 끝납니다. 킹이 된 말은 다음 차례가 오기 전까지 새로 뛰어넘기를 시작하거나 이어갈 수 없습니다.
한 번의 이동 동안 같은 말을 두 번 이상 뛰어넘을 수는 없습니다(킹이 연속 점프를 할 때만 문제가 됩니다).

이동은 움직이는 말이 지나는 칸 번호들을 붙임표(-)로 이어 적습니다. 예를 들어 22-18은 White의 단순 이동이고, 14-23은 18번 칸의 White 말을 잡는 Red의 뛰어넘기이며, 22-31-24-15는 White 킹이 26, 27, 19번의 Red 말을 잡는 연속 점프입니다.

진행 중인 대국의 한 배치와, 그 배치에서 적용할 이동들의 목록이 주어집니다. 모든 이동이 규칙에 맞는지 판정하세요.

입력

입력에는 여러 개의 대국 인스턴스가 들어 있습니다. 각 인스턴스는 판 위의 Red 말 수 $r$ 과 White 말 수 $w$ 두 정수로 시작합니다( $1 \le r, w \le 12$ ). $r = w = 0$ 인 줄은 입력의 끝을 뜻합니다.

다음 줄에는 Red 말이 놓인 칸 $r$ 개가, 그 다음 줄에는 White 말이 놓인 칸 $w$ 개가 나옵니다. 값이 양수 $sq$ 이면 $sq$ 번 칸에 일반 말이, 음수 $-sq$ 이면 $sq$ 번 칸에 킹이 놓여 있음을 뜻합니다.

그 다음 줄에는 정수 $m \ge 1$ 과 문자 하나(R 또는 W)가 나와, 이동 횟수와 먼저 두는 쪽을 나타냅니다. 이어지는 $m$ 개의 줄에는 위 표기법에 따른 이동이 한 줄에 하나씩 주어집니다(한 이동에 칸 번호는 최대 13개).

주어지는 모든 배치는 규칙에 맞으며(같은 칸에 두 말이 놓이는 일은 없습니다), 이미 승격 줄에 있는 말은 모두 킹입니다.

출력

각 인스턴스마다, 모든 이동이 규칙에 맞으면 All moves valid를 출력합니다. 그렇지 않으면 Move n is invalid를 출력하며, 여기서 이동 1은 그 인스턴스의 첫 번째 이동입니다. 규칙에 어긋나는 이동이 여럿이면 가장 먼저 나오는 것 하나만 보고합니다.