No testdata at current.

AI 机器人

时空限制

• CPU占用时长: 1秒
• 内存使用限制: 128MB

题目描述

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

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

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

$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$ 个字符，描述了矩形空���。其中半角点号为平地、井号为障碍物。

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

输出格式

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

输入输出样例

样例 1

输入：

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

输出：

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

样例 2

输入：

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

输出：

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

样例 3

输入：

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

输出：

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

数据范围与提示

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

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

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

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