B. Braid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice loves braids! Her preferred hairstyle for as long as anyone has known her has always been some kind of braid.

One day, Bob asked Alice if she could teach him how to do a simple braid. Alice, excited, gave him the following instructions for a basic braid.

  • Split the hair into three sections.
  • For $$$n$$$ times, take two adjacent sections and cross one over the other.
    • We alternate between crossing the left-over-middle and right-over-middle.
    • The initial crossing is up to you.

Bob didn't quite understand, so Alice created the following image to hopefully explain things more clearly. Here is an example braid with $$$n = 7$$$ crossings that begins with left-over-middle.

Ah, now Bob gets it! He thanks Alice for the helpful image.

Alice thinks that the image was so helpful that they should make more. Given the number of crossings $$$n$$$, the initial crossing, and a string $$$s$$$ which encodes the colors we would use for the three sections, output a similar drawing of a braid, using ASCII art. See the Output Format and Sample I/O for more details.

Input

The first line of input contains a single integer $$$n$$$, the number of crossings in the braid.

The second line of input contains either left-over-middle or right-over-middle, indicating which is the initial crossing in the braid.

The third line of input contains a single string $$$s$$$ with three distinct uppercase letters, which represent the colors of the sections from left to right.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 50 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline

1 & \mathbf{33} & n = 1 \\ \hline

2 & \mathbf{33} & \text{The initial crossing is }\mathtt{left-over-middle}\text{.} \\ && s = \text{ABC} \\ \hline

3 & \mathbf{34} & \text{No further constraints.} \\ \hline

\end{array}\\

\end{align*}$$$$$$

Output

Output an ASCII grid with $$$9$$$ columns and $$$1+4n$$$ rows, representing the braid.

The first row contains the first, second, and third letters of $$$s$$$ in the $$$1$$$st, $$$5$$$th, and $$$9$$$th columns, respectively, representing the three sections as originally positioned from left to right, with their respective colors.

Each of the $$$n$$$ crossings is represented by another four rows. Examine the samples to see, for each crossing, how to render the section that goes over, the section that goes under, and the section that is unused. Place a . on every "empty" square of the grid which does not contain a section.

Examples
Input
1
left-over-middle
ABC
Output
A...B...C
.A.B....C
..A.....C
.B.A....C
B...A...C
Input
2
right-over-middle
ABC
Output
A...B...C
A....B.C.
A.....C..
A....C.B.
A...C...B
.A.C....B
..A.....B
.C.A....B
C...A...B
Input
7
left-over-middle
NOI
Output
N...O...I
.N.O....I
..N.....I
.O.N....I
O...N...I
O....N.I.
O.....I..
O....I.N.
O...I...N
.O.I....N
..O.....N
.I.O....N
I...O...N
I....O.N.
I.....N..
I....N.O.
I...N...O
.I.N....O
..I.....O
.N.I....O
N...I...O
N....I.O.
N.....O..
N....O.I.
N...O...I
.N.O....I
..N.....I
.O.N....I
O...N...I