The game of checkers is played on an 8 by 8 red-black board using alternate squares. Two players (Red and White) each start with 12 pieces which are set up in the starting position shown below: Rules for movement and capture are as follows (Note: a forward move is one in which a piece moves towards the opponent’s side of the board):
2/2 Input Input will consist of multiple problem instances. Each instance will start with two integers r and w, indicating the number of Red and White pieces on the board (values of r = w = 0 indicates end of input, otherwise 1 ≤ r, w ≤ 12). The next line will contain r square numbers indicating the Red piece positions and the next line will contain w square numbers for the White piece positions. Positive square values will indicate that a normal piece lies on that square, while a negative value −sq will indicate that a promoted piece lies on square sq. The next line will contain a single integer m ≥ 1 indicating the number of moves to make, followed by a space and then a single character (either ‘R’ or ‘W’) indicating whose move it is. The next m lines will contain the m moves, using the notation described above. (You may assume that there are no more than 13 square numbers listed in any one move.) All board positions will be legal positions (e.g., there will never be two pieces occupying the same square). You may assume that pieces that have advanced to their promotion row are indeed promoted; that is, there will be no pieces on their promotion row that are not kings. Output For each problem instance, output either ‘All moves valid or ‘Move n is invalid’, where n = 1 corresponds to the first move in the problem instance. If there are multiple illegal moves, you should list only the first such move. Sample Input 43 6 7 8 -16 9 18 19 3W 9-2 16-23-14 2-11-4 43 6 10 15 19 18 22 23 6R 19-26 18-11 10-14 22-18 6-10 10-15 00 Sample Output All moves valid Move 5 is invalid