Robot Program Reachability

In an $n\times m$ rectangular grid, each cell is either free (denoted by a dot .) or an obstacle (denoted by a hash #). A robot initially starts at the top‐left cell (row 1, column 1). The robot executes a program which is a sequence of commands. The basic commands are:

• U for up,
• D for down,
• L for left,
• R for right.

When the robot executes a basic command it attempts to move one cell in the corresponding direction. If the target cell is out‐of‐bounds or contains an obstacle, the robot remains in place.

The program may also contain loops with the following syntax:

• (P)n which means to repeat the sub‐program P exactly $n$ times (by copy–paste semantics).
• (P)* which indicates an artificial intelligence (AI) loop. In this loop the number of repetitions is chosen arbitrarily (i.e. it can be 0 or any positive number). AI loops can be nested; however, the outer loops are fixed before the inner loops are "unfolded" (again by copy–paste semantics).

For example, executing the program (R(DRUL)7)5 in a sufficiently large obstacle–free grid will move the robot right one cell then perform 7 copies of DRUL (which is a cyclic movement) and then this entire block is repeated 5 times. In a grid of size $1\times2$, the same program would result in lateral jumping.

Given the grid and a robot program, determine which cells are guaranteed never to be visited by the robot regardless of how the non–deterministic choices in the AI loops are resolved. In the output grid, obstacles remain as is (#), free cells that may be visited in some execution of the program are marked with ., and free cells that are never visited in any execution are marked with 0.

inputFormat

The first line contains two integers $n$ and $m$ --- the number of rows and columns of the grid.

The next $n$ lines each contain a string of $m$ characters where each character is either . (free cell) or # (obstacle).

The last line of input is a non–empty string representing the robot program. The program consists of commands U, D, L, R and loops of the form (P)n or (P)* where P is a valid (possibly nested) sub–program and n is a positive integer.

outputFormat

Output $n$ lines, each line containing $m$ characters. For each cell:

• If the cell is an obstacle (#), output #.
• If the cell is free and the robot may visit it in some execution of the program, output ..
• If the cell is free and the robot will never visit it regardless of choices in AI loops, output 0.

sample

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

...#000
00.#000
00.....