Hex Operations
time limit per test
2 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

In this problem, a hex is a six-sided board consisting of cells: small regular hexagons. A hex of size $$$n$$$ has $$$n$$$ cells on each side. Each cell contains an integer.

Consider the following operations with a hex:

- "T": reflect the hex over its vertical symmetry axis,
- "R": rotate the hex 60 degrees clockwise,
- "L": rotate the hex 60 degrees counter-clockwise.

Here is an example of a hex of size $$$n = 3$$$ and operations with it:

You are given a hex and a sequence of operations. Perform all the given operations in order and print the resulting hex.

Input

The first line contains an integer $$$n$$$, the size of the hex ($$$2 \le n \le 500$$$). The next $$$2 n - 1$$$ lines contain integers from $$$1$$$ to $$$99$$$ initially contained in the cells of the hex. Each line contains space-separated integers: exactly as many as the number of cells in the corresponding row of the hex. Additionally, for ease of reading, these lines may contain additional spaces before all numbers, between consecutive numbers, and after all numbers.

The last line is the sequence of operations. It has a length from $$$1$$$ to $$$250\,000$$$ characters and consists of letters "T", "R" and "L".

The total size of the input, including spaces and line breaks, does not exceed $$$2^{23}$$$ bytes.

Output

Print the hex after performing all operations: $$$2 n - 1$$$ lines containing integers. Each line should contain several space-separated integers: exactly as many as the number of cells in the corresponding row of the hex. Additionally, for ease of reading, these lines may contain additional spaces before all numbers, between consecutive numbers, and after all numbers.

The total size of the output, including spaces and line breaks, should not exceed $$$2^{23}$$$ bytes.

Example

Input

    3
      4 1 8
     3 5 1 7
    2 1 6 1 8
     1 7 1 9
      8 9 9
    LTR

Output

      9 9 8
     9 1 1 7
    8 7 6 1 8
     1 1 5 1
      2 3 4