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:
Figure C.1: (a), (b) The first two moves in Sample Input 1. The larger pieces are kings and the smaller ones are men. Black sits at the top and White at the bottom. (c) Numbering used in the input.
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 in {mathtt(B), mathtt(W)}$ indicates which player makes the first move (Black or White respectively) and $n$ ($1 <= n <= 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–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 times b_1 times b_2 times \\\\cdots times 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.
## Input
The first line of input contains a character $c$ and an integer $n$, where $c in {mathtt(B), mathtt(W)}$ indicates which player makes the first move (Black or White respectively) and $n$ ($1 <= n <= 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–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 times b_1 times b_2 times \\\\cdots times b_k$.There is always a valid solution for the given set of moves.
## Output
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.
[samples]
**Definitions**
Let $ (X, Y) \in \mathbb{Z}^2 $ be Maria’s initial position.
Let $ N \in \mathbb{Z}^+ $ be the number of seconds (steps).
Let $ D \in \mathbb{Z}_{\geq 0} $ be the minimum allowed Manhattan distance from $ (0, 0) $.
Let $ \mathcal{P}_N $ be the set of all $ N $-step walks starting at $ (X, Y) $, where each step moves one unit in one of the four cardinal directions: $ \{(1,0), (-1,0), (0,1), (0,-1)\} $.
**Constraints**
1. $ |X|, |Y| \leq 1500 $, $ |X| + |Y| > D $
2. $ 1 \leq N \leq 1500 $
3. $ 0 \leq D \leq 4 $
4. For every position $ (x, y) $ along the walk (including intermediate steps), it must hold:
$$
|x| + |y| > D
$$
**Objective**
Compute the number of valid $ N $-step walks starting at $ (X, Y) $, such that at every step $ t \in \{0, 1, \dots, N\} $, the Manhattan distance from $ (0, 0) $ is strictly greater than $ D $:
$$
\left| \left\{ \text{walks } w \in \mathcal{P}_N \,\middle|\, \forall t \in \{0, \dots, N\}, \, |x_t| + |y_t| > D \right\} \right| \mod (10^9 + 7)
$$