题目描述

在 $n$ 行 $m$ 列的矩形空间中有一个机器人。矩形空间的每一个格子要么是平地（用半角点号 . 表示），要么是障碍物 （用井号表示 #）。以下是一个 $n = 3, m = 7$ 的例子：

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

初始时,机器人位于矩形的左上角 （第一行、第一列）。每一时刻，机器人可以遵照程序执行 U（Up，向上）、L （Left，向左）、 D （Down，向下）、R （Right，向右） 四种指令中的一个，尝试向某个方向移动一格；如果移动的目标格子超出了边界或是障碍物，则保持原地不动，例如执行程序：

LLLRRRRRRRRRDDDDRRRRRRRRR

后，机器人会从空间的左上角移动到右下角。Dr. X 扩展了机器人程序的表达能力,引入了循环。给定程序 P，(P)n 相当于把程序 P“复制粘贴”$n$ 次。循环可以嵌套。例如，在足够大且无阻挡的空间中执行程序：

(R(DRUL)7)5

会重复 $5$ 次执行“向右移动一格、转圈 $7$ 次”，而如果机器人在 $n = 1, m = 2$ 的空间中执行上述程序，就会表现为“左右横跳”。

Dr. X 还给机器人装备了人工智能，对于某些指定的循环，机器人可以由深度神经网络自主决定循环的次数（$0$ 次或任意多次），用星号 * 表示，例如

(DR(R)*)3

外层循环会执行 $3$ 次，由于循环“复制粘贴”的特性，每次向下向右移动一格后，机器人可以根据自己的想法向右移动 $0$ 格或任意多格。人工智能循环也可以嵌套，根据循环“先外层后里层”的执行顺序，总是先确定外层人工智能循环的执行次数，再按照“复制粘贴”的规则执行内层循环代码。

人工智能模块使机器人的行为变得难以预测。给定一个机器人程序，Dr. X 想知道，哪些格子是机器人在执行程序过程中绝无可能经过的（即无论机器人如何选择循环执行的次数，都不会经过）？这样他可以在这些格子上安装监控，并在观察到机器人行为失控的时候及时制止。

输入格式

输入第一行两个空格分隔的整数 $n$ 和 $m$，代表矩形空间的大小为 $n$ 行、$m$ 列。

接下来 $n$ 行，每行 $m$ 个字符，描述了矩形空间。其中半角点号为平地、井号为障碍物。

输入最后一行是一个字符串，为机器人执行的程序。程序由 $\tt{U/L/D/R}$、圆括号、正整数、星号组成。输入程序保证合法：圆括号总是正确配对，且之后紧跟一个正整数或一个星号。除此之外，程序中所有的字符都是 $\tt{U,L,D}$ 或 $\tt{R}$。机器人初始时位于左上角，输入保证左上角不是障碍物。固定次数循环的次数总是在 $1$ 到 $9$ 之间。

输出格式

输出 $n$ 行，每行 $m$ 个字符，按顺序输出矩形空间中每个格子的计算结果。如果是障碍物格子，输出井号 #。如果是机器人选择适当的循环次数可以到达的平地格子，输出加号 +。否则输出半角点号 .。

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

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

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

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

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

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

提示

对于 $30\%$ 的数据，输入程序不含星号 * 且在 $10^5$ 步内终止。

对于另外 $30\%$ 的数据，输入程序中不含星号 *。

对于 $100\%$ 的数据，$1 \leq n, m \leq 10$，且输入程序的长度不超过 $1000$。

本题原始满分为 $20\text{pts}$。