Problem Description

In a rectangular space of $n$ rows and $m$ columns, there is a robot. Each cell in the rectangular space is either a flat ground (represented by a dot . ) or an obstacle (represented by a hash #). Here is an example for $n = 3, m = 7$:

...#...
...#...
.......

Initially, the robot is located at the top-left corner (first row, first column). At each moment, the robot can follow a program to execute one of four instructions: U (Up), L (Left), D (Down), R (Right), attempting to move one cell in a direction. If the target cell is out of bounds or an obstacle, the robot stays in place. For example, after executing the program:

LLLRRRRRRRRRDDDDRRRRRRRRR

the robot will move from the top-left corner to the bottom-right corner. Dr. X has enhanced the robot's program capabilities by introducing loops. Given a program P, (P)n means to "copy and paste" the program P $n$ times. Loops can be nested. For example, in a sufficiently large and unobstructed space, executing the program:

(R(DRUL)7)5

will repeat 5 times the action of moving right one cell and circling 7 times. If the robot executes this program in a space of $n = 1, m = 2$, it will appear to "bounce left and right".

Dr. X has also equipped the robot with artificial intelligence. For certain specified loops, the robot can decide the number of loop executions (0 or any number of times) autonomously, represented by an asterisk *. For example,

(DR(R)*)3

the outer loop will execute 3 times. Due to the "copy and paste" nature of loops, after moving down and right once each time, the robot can choose to move right 0 or any number of times based on its own decision. AI loops can also be nested. According to the execution order of "outer layer first, then inner layer", the number of executions for the outer AI loop is always determined first, and then the inner loop code is executed according to the "copy and paste" rule.

The AI module makes the robot's behavior unpredictable. Given a robot program, Dr. X wants to know which cells the robot will never pass through during program execution (i.e., no matter how the robot chooses the number of loop executions, it will not pass through). This way, he can install monitors on these cells and intervene promptly when observing失控 behavior.

Input Format

The first line of input contains two space-separated integers $n$ and $m$, representing the size of the rectangular space as $n$ rows and $m$ columns.

The next $n$ lines, each containing $m$ characters, describe the rectangular space. A dot . represents flat ground, and a hash # represents an obstacle.

The last line is a string representing the robot's program. The program consists of U/L/D/R, parentheses, positive integers, and asterisks. The input program is guaranteed to be valid: parentheses are always correctly paired and followed by a positive integer or an asterisk. All other characters in the program are U, L, D, or R. The robot starts at the top-left corner, and the input guarantees that the top-left corner is not an obstacle. The number of fixed-time loop executions is always between 1 and 9.

Output Format

Output $n$ lines, each containing $m$ characters, in order to represent the calculation results for each cell in the rectangular space. If a cell is an obstacle, output a hash #. If a cell is a flat ground that the robot can reach by choosing appropriate loop counts, output a plus +. Otherwise, output a dot ..

Sample Input and Output

Sample Input #1

3 7
...#...
...#...
.......
LLLRRRRRRRRRDDDDRRRRRRRRR

Sample Output #1

+++#...
..+#...
..+++++

Sample Input #2

3 7
...#...
##.....
.......
(R(DRUL)7)5

Sample Output #2

+++#...
##+++++
..+++++

Sample Input #3

3 7
.......
.#####.
.......
(R)*(D)*

Sample Output #3

+++++++
+#####+
+.....+

Notes/Hints

For $30\%$ of the data, the input program does not contain an asterisk * and terminates within $10^5$ steps.

For another $30\%$ of the data, the input program does not contain an asterisk *.

For $100\%$ of the data, $1 \leq n, m \leq 10$, and the length of the input program does not exceed $1000$.

This problem originally had a full score of $20\text{pts}$.

见题面 Input 部分

见题面 Output 部分