Problem Description

There is a robot that reads a sequence of commands and walks on a board. In this problem, a command is one of three characters: S, L, R, and a command sequence is a string consisting of these characters.

You are given $N$ ($= 500$) command sequences of length $L$ ($= 300$). Your task is to construct an $M \times M$ ($M = 29$) board to make the robot stop at as scattered positions as possible for the $N$ command sequences.

The robot starts at the center of the board (15th cell from the top and left) facing up and executes the commands in the sequence from left to right. The effect of each command is as follows:

• S: Move one cell in the current direction.
• L: Rotate 90 degrees to the left.
• R: Rotate 90 degrees to the right.

However, you can use cells that influence the effect of these commands to construct the board. The available cells are as follows:

• .: Normal cell. Commands executed on this cell have their original effect.
• #: Wall cell. If the robot attempts to move into this cell, the move fails, and the robot stays in the previous cell. The outermost cells of the board must all be wall cells.
• D: Double cell. The effect of a command executed on this cell is applied twice in a row (effects of cells passed through in between are ignored).
• T: Triple cell. The effect of a command executed on this cell is applied three times in a row (effects of cells passed through in between are ignored).
• L: L cell. Executing command R on this cell has the same effect as executing L on a normal cell.
• R: R cell. Executing command L on this cell has the same effect as executing R on a normal cell.

You can use any number of these cells.

To reiterate your task, construct a board such that the robot stops at as scattered positions as possible for the $N$ command sequences. More specifically, your constructed board will be scored as follows:

• Initialize the stop count of each cell to 0.
• For each command sequence, let the robot execute the sequence starting from the center cell, and increment the stop count of the cell where the robot stands at the end of the execution.
• Score each cell as follows:
• If the stop count is 1, the cell's score is 10 points.
• If the stop count is 2, the cell's score is 3 points.
• If the stop count is 3, the cell's score is 1 point.
• Otherwise, the cell's score is 0 points.
• The score of the board is the sum of the scores of all cells.

Construct a board to achieve the highest possible score.

Input Format

The input is given in the following format:

$N$ $M$ $L$ $S_1$ $S_2$ $ : $ $S_N$

Output Format

Output the board that achieves the highest possible score in the following format:

$T_1$ $T_2$ $ : $ $T_M$

Here, $T_i$ is a string of length $M$ and can only contain the characters ., #, D, T, L, R.

Also, the outermost characters of the board (i.e., all characters in $T_1$ and $T_M$, and the first and last characters of each $T_i$) must all be #, and the 15th character of $T_{15}$ must not be #.

Sample Input and Output

Sample Input #1

6 7 7
RSLSSRS
RSSLSSS
SRSLLLL
RSLSLLL
LSLSLLL
RRSRSRR

Sample Output #1

#######
#....##
#..L..#
#.T...#
#..D..#
#R....#
#######

Sample Input #2

Sample Output #2

None

Notes/Hints

Constraints

• $N = 500$
• $M = 29$
• $L = 300$
• $S_i$ is a string of length $L$.
• Each character in $S_i$ is chosen independently, with a 50% probability of being S, a 25% probability of being L, and a 25% probability of being R.

Scoring

The score for a single test case is calculated as described in the problem statement.

There are 30 test cases, and the sum of the scores for all test cases is the score for the submission.

Note that if the output is invalid for any test case other than example_01, the score for all test cases other than example_01 will be 0.

Sample Explanation 1

This input is a small-sized example for illustration and does not satisfy the constraints. For each command sequence, the robot stops at the following cells, earning 60 points:

#######
#.5.1##
#.3642#
#.....#
#.....#
#.....#
#######

Sample Explanation 2

Input file and output example are available here (zip) The scoring result for "example_01" is based on this data. This data is also part of the scoring.

见题面 Input 部分

见题面 Output 部分