题目内容

布展开始前，展馆打算让一台喷涂机器人在地上留下记号。整块场地切成 $h$ 行、$w$ 列的方格，自上往下行号依次是 $1\sim h$，自左往右列号依次是 $1\sim w$。方格写作 . 代表可通行的空格，写作 # 代表承重柱。机器人无法踏入承重柱，也无法跑出场地。

所有空格各自带一个颜色值，开始时全是 $0$。机器人每到达某个空格一次，那一格的颜色值便沿着 $0\to 1\to 2\to 0$ 轮换一步；机器人刚出发时，出发格同样计作到达一次。

机器人依据一段命令串 $P$ 来行动，$P$ 由下面几类片段拼成：

• F：顺着当前面朝的方向往前挪一格；
• L：在原位向左旋转 $90^\circ$；
• R：在原位向右旋转 $90^\circ$；
• t(Z)：循环片段。$t$ 为 $1\sim 99$ 范围内的整数，$Z$ 是仅由 F、L、R 构成的非空串，含义是把 $Z$ 接连执行 $t$ 轮。比如 2(FR) 的效果与 FRFR 相同。括号之间不存在嵌套。

命令按以下方式生效：

1. 处理 F 时，若面前的格子是空格，机器人就走进去，同时令这一格的颜色值轮换一步；
2. 处理 F 时，若面前是承重柱或者场地外，机器人不挪动，转而在原位向右旋转 $90^\circ$，这种情况称作一次碰壁，任何格子的颜色值均不受影响；
3. 机器人会累计连续碰壁的次数：每碰壁一次计数增加 $1$，一旦顺利前进一格就归零；L、R 两种命令与该计数无关；
4. 连续碰壁的计数一达到 $4$，机器人当即关机，剩余全部命令（循环片段里还没轮到的部分也算在内）一律作废。

最后需要给出机器人停下时的所在格与面朝方向，以及场地内每一格的颜色值。

输入描述

第一行给出两个整数 $h$ 与 $w$。

随后 $h$ 行，每行是一个长为 $w$ 的字符串，字符只有 . 与 #，用来刻画场地。

再往下一行给出两个整数 $a,b$ 以及一个字符 $c$，意思是出发格位于第 $a$ 行第 $b$ 列，起初面朝 $c$。$c$ 只会是 U、D、L、R 中的一个，依次对应上、下、左、右。

末行给出命令串 $P$。

输出描述

首行打印两个整数与一个字符，按顺序为机器人最后所处的行号、列号与面朝方向。

之后输出 $h$ 行，每行为长 $w$ 的字符串：空格处写出它的颜色值（0、1 或 2），承重柱处写 #。

数据范围：

• $1\le h,w\le 100$
• $1\le |P|\le 1000$
• 出发格一定是空格。
• 命令串的格式一定合法：循环片段里的 $t$ 不带前导零，括号两两配对且不嵌套，括号里不为空且只出现 F、L、R。

样例1

输入

3 5
..#..
.....
..#..
1 1 R
4(F)R2(F)RF

输出

3 2 R
11#00
01000
12#00

说明

把命令串摊开后是 FFFF R FF R F。

• 出发那一刻，$(1,1)$ 的颜色值成为 $1$，面朝右；
• FFFF：第 $1$ 个 F 走到 $(1,2)$；第 $2$ 个 F 正前方 $(1,3)$ 为承重柱，碰壁，右转以后面朝下，连续碰壁计数是 $1$；第 $3$、$4$ 个 F 先后走到 $(2,2)$、$(3,2)$，计数归零；
• R：由面朝下右转为面朝左；
• FF：第 $1$ 个 F 走到 $(3,1)$；第 $2$ 个 F 正前方已在场地外，碰壁，右转以后面朝上，计数是 $1$；
• R：由面朝上右转为面朝右；
• F：重新走进 $(3,2)$，这一格的颜色值从 $1$ 轮换到 $2$。

机器人最后停在 $(3,2)$，面朝右。

样例2

输入

2 3
.#.
##.
1 1 D
2(LF)3(F)F

输出

1 1 U
1#0
##0

说明

出发那一刻，$(1,1)$ 的颜色值成为 $1$，面朝下。

• 第 $1$ 轮 LF：L 之后面朝右；F 正前方 $(1,2)$ 为承重柱，碰壁，右转以后面朝下，连续碰壁计数是 $1$；
• 第 $2$ 轮 LF：L 之后面朝右，计数保持不变；F 又撞上 $(1,2)$，碰壁，右转以后面朝下，计数是 $2$；
• 3(F) 里的第 $1$ 个 F：正前方 $(2,1)$ 为承重柱，碰壁，右转以后面朝左，计数是 $3$；
• 3(F) 里的第 $2$ 个 F：正前方已在场地外，碰壁，右转以后面朝上，计数到达 $4$，当即关机。

3(F) 里剩下的那个 F 以及末尾的 F 全部作废。机器人最后停在 $(1,1)$，面朝上；最右一列始终没被到达过，颜色值仍是 $0$。