题目背景

Warning: If you submit a malicious program, you will be banned.

警告：恶意提交本题将被封号。

题目描述

Your university's board game club just hosted a Checkers tournament, and you were assigned to take notes on the games. Unfortunately, while walking home, you dropped all of your papers into a puddle! Disaster! Much of what you wrote is now unreadable; all you have left are some lists of moves played in the middle of various games. Is there some way you can reconstruct what happened in those games? You had better fix things fast, or they will demote you to Tic-Tac-Toe recordkeeper!

Checkers (or English Draughts) is a well-known board game with simple rules. It is played on the dark squares of an $8 \times 8$ checkerboard. There are two players, Black and White, who alternate turns moving their pieces (all of Black's pieces are black and all of White's pieces are white). Each piece occupies a single dark square, and can be either a normal $man$ or a promoted $king$. A turn consists of choosing one piece and moving it in one of two ways:

1. Shifting it diagonally to an unoccupied adjacent dark square, as shown in Figure C.1(a). This is called a $simple~move$. If the piece is a man, it can move only in the two diagonal directions towards the opposing side of the board (towards the bottom for Black, the top for White). If the piece is a king, it can move in all four diagonal directions.

2. Jumping over an adjacent enemy piece to an unoccupied square immediately on the other side, then removing ($capturing$) that piece. Men can jump only in the two directions described above, while kings can jump in all four. The player can then repeat this step, continuing to jump with the same piece as long as there are properly-positioned enemy pieces to capture. Such a sequence of one or more jumps is called a $jump~move$. Figure C.1(b) shows a jump move comprising three jumps.

In Checkers, captures are forced moves. If a jump move is available at the start of a player's turn, they must jump, and cannot stop jumping with that piece until it has no more possible jumps. They are free to choose which piece to jump with, and where, if there are multiple possibilities. In Figure C.1(b), Black could not have made any other move.

If a man reaches the farthest row from its player (that is, a black man reaches the bottom row or a white man reaches the top row), it is removed from the board and replaced by a king of the same color (it is said to be $promoted$), and the turn ends. A piece cannot be promoted and then jump backwards as a new king in the same turn.

Given a list of moves, find a setup of pieces such that the moves can be legally played in sequence starting from that setup. This setup may not have black men on the bottom row or white men on the top row, since they would have been promoted to kings already. You need only ensure that the rules above are obeyed; you do not need to ensure that this setup is reachable in a real game of Checkers.

输入格式

The first line of input contains a character $c$ and an integer $n$, where $c$ is either B or W, indicates which player makes the first move (Black or White respectively) and $n$ ($1 \leq n \leq 100$) is the number of moves in the list. Then follow $n$ lines, each of which describes a move in the standard Checkers notation defined below.

The dark squares are identified by numbers $1 \sim 32$, as shown in Figure C.1(c). A simple move from square $a$ to square $b$ is written as a-b. A jump move starting at $a$ and jumping to $b_1, b_2, \dots , b_k$ is written as $a\text{x}b_1\text{x}b_2\text{x} \dots \text{x}b_k$.

There is always a valid solution for the given set of moves.

输出格式

Output two boards side-by-side (separated by a space), giving the positions of all pieces on the board before (on the left) and after (on the right) the given moves. Use - for light squares, . for empty dark squares, lowercase b and w for black and white men, and uppercase B and W for black and white kings. If there is more than one valid solution, any one is acceptable.

题目大意

游戏在一个 $8 \times 8$ 的方格棋盘的深色方格上进行。有两名玩家，黑方和白方，他们轮流移动他们的棋子（所有黑方的棋子都是黑色的，所有白方的棋子都是白色的）。每个棋子占据一个单独的深色方格，可以是兵或王。一个回合包括选择一个棋子并以以下两种方式之一移动它：

1. 将其斜着移动到一个相邻的未占用的深色方格，如图 (a) 所示。这被称为简单移动。兵只能沿向前的两种方向移动（对于黑方是朝下，对于白方是朝上）。如果棋子是王，它可以在所有四个斜方向移动。

2. 跳过对方的棋子到达空地，并吃掉对方的子。允许移动的方向与第一条相同。然后，玩家可以重复此步骤，继续使用相同的棋子跳。这样一个或多个跳的序列称为跳跃移动。图 (b) 展示了由三个跳跃组成的跳跃移动。

如果在玩家回合开始时有一个跳跃移动可用，他们必须进行跳跃，并且不能停止使用该棋子跳跃，直到它没有更多可能的跳跃。他们可以自由选择使用哪个棋子进行跳跃，以及在有多个可能性的情况下选择在哪里跳跃。在图 (b) 中，黑方不能进行任何其他移动。

如果一个兵达到其玩家的最远一行（即，一个黑子达到底行或一个白子达到顶行），它将变成同色的王（称为晋升），然后回合结束。这意味着一个兵不能在同一回合中被晋升然后以王的身份继续倒退跳跃。

给定一系列移动，请找到一个初始棋局，使得可以从该棋局开始按顺序合法进行这些移动。此棋局可能不能在底行有黑子或在顶行有白子，因为它们可能已经被晋升为王。你只需要确保上述规则被遵守；不需要确保这个棋局在实际跳棋游戏中是可达的。

输入格式

输入的第一行包含一个字符 $c$ 和一个整数 $n$，其中 $c$ 是 B 或 W，表示哪个玩家首先移动（分别为黑方或白方），$n$（$1 \leq n \leq 100$）是移动列表中的移动次数。然后是 $n$ 行，每行描述标准跳棋符号中定义的一步移动。

深色方格用数字 $1 \sim 32$ 标识，如图 (c) 所示。从方格 $a$ 到方格 $b$ 的简单移动写作 a-b。从 $a$ 开始跳到 $b_1, b_2, \dots , b_k$ 的跳跃移动写作 $a\text{x}b_1\text{x}b_2\text{x} \dots \text{x}b_k$。

对于给定的移动集合，总是存在至少一个答案。

输出格式

所有棋子在棋盘上的位置以两个并排的棋盘输出（用空格分隔），分别表示在给定的移动之前（左边）和之后（右边）的棋盘。

使用-表示浅色方格，.表示空的深色方格，小写的b和w表示黑色和白色兵，大写的B和W表示黑色和白色王。如果存在多个答案，则任何一个都可以接受。

W 3
21-17
13x22x31x24
19x28

-b-.-.-. -b-.-.-.
.-.-.-.- .-.-.-.-
-.-.-.-. -.-.-.-.
B-.-w-.- .-.-w-.-
-.-.-W-. -.-.-.-.
w-.-.-.- .-.-.-.-
-.-w-w-. -.-.-.-W
.-.-.-.- .-.-.-.-

B 5
2-7
9x2
32-27
2x11x18
5-9

-.-b-.-W -.-.-.-W
b-b-.-.- .-.-.-.-
-w-.-.-. -b-.-.-.
B-w-b-.- B-w-.-.-
-.-.-.-. -.-W-.-.
.-.-.-.- .-.-.-.-
-.-.-.-. -.-.-B-.
.-.-.-B- .-.-.-.-

提示

Source: ICPC World Finals 2019.