I. Image of the Artist as Filipino
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob decided that it would be fun to experiment with other mediums of art in his spare time. He started to enjoy art (and life!) a lot more when realized that he can just try out new and exciting things, without needing "permission" from an "official" curriculum. People he perceives as experts, or as ones living exciting lives, actually earned those labels by being proactive with their life experiences.

Today, Bob is playing around with stained glass tile mosaics!

Bob's mosaic can be described as an $$$n \times n$$$ grid, where each cell contains a translucent square tile that is colored either red or blue. Each tile is completely indistinguishable from any other tile of the same color, even if you rotate it around or flip it over. Bob hung the mosaic on a frame on the wall.

Cindy, enthralled by the art, wanted to observe it from a bunch of different angles. To that effect, she picked up the mosaic and applied some sequence of movements to the it. We can break these movements up into four main types of operations, which we show below.

We describe (and encode) these operations as follows.
  • L to rotate the mosaic $$$90^\circ$$$ counter-clockwise
  • R to rotate the mosaic $$$90^\circ$$$ clockwise
  • H to reflect the mosaic horizontally (across its vertical axis)
  • V to reflect the mosaic vertically (across its horizontal axis)

Unfortunately, when she was done, Cindy couldn't remember what the original mosaic looked like! However, she does remember the exact sequence of operations she performed. Given that information, please help Cindy recover the appearance of the original mosaic before Bob finds out.

Input

The first line of input contains a single integer $$$n$$$.

Then, $$$n$$$ lines follow, each containing a string of length $$$n$$$. This encodes the $$$n \times n$$$ mosaic after all the operations have been performed. The colors red and blue are represented by # and . characters.

The next line contains the string $$$s$$$, encoding the operations in the order that they are performed on the mosaic. Each operation is described by a letter whose meaning is given above.

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 3 \leq n \leq 750 \\ 1 \leq |s| \leq 5 \times 10^5 \\ \hline \end{array}\\

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

1 & \mathbf{20} & n = 3 \\ \hline

2 & \mathbf{25} & n \leq 12 \\ && \text{There are no }\mathtt{L}\text{ or }\mathtt{R}\text{ commands.} \\ && |s| \leq 1000 \\ \hline

3 & \mathbf{25} & n \leq 12 \\ && |s| \leq 1000 \\ \hline

4 & \mathbf{16} & \text{There are no }\mathtt{L}\text{ or }\mathtt{R}\text{ commands.} \\ \hline

5 & \mathbf{14} & \text{No further constraints.} \\ \hline

\end{array}\\

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

Output

Output $$$n$$$ lines, each containing a string of $$$n$$$ characters. This should represent the original mosaic before all the operations were performed.

Examples
Input
3
.#.
.#.
##.
RHL
Output
##.
.#.
.#.
Input
12
............
......#.....
....#.#.#...
....#.#.#...
..#.#.#.#...
..#.#.#.#...
..#.#.#.#.#.
..#######.#.
..#########.
...#######..
....#####...
....#####...
LVR
Output
............
.....#......
...#.#.#....
...#.#.#....
...#.#.#.#..
...#.#.#.#..
.#.#.#.#.#..
.#.#######..
.#########..
..#######...
...#####....
...#####....
Input
12
...######...
..#......#..
.#......#.#.
#..#..#.#..#
#.#.....#..#
#.#.#......#
#.#.##.....#
#.#.....#..#
#..#..#.#..#
.#......#.#.
..#......#..
...######...
LHRVLLHRHLHVRHRLRVR
Output
...######...
..#......#..
.#........#.
#.###..###.#
#..........#
#..#....#..#
#.....#....#
#....##....#
#..#....#..#
.#..####..#.
..#......#..
...######...
Input
5
..#..
.###.
#.#.#
..#..
..#..
VRHL
Output
..#..
.###.
#.#.#
..#..
..#..