题目描述

有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i,j)$ 表示从上往下第 $i$ 行，从左往右第 $j$ 列的单元格。

如果 $S_{i,j}$ 是 #，那么 $(i,j)$ 单元格是无法通过的；

如果 $S_{i,j}$ 是 .，那么该单元格是可以通过的，此处没有硬币；

如果 $S_{i,j}$ 是 @，那么该单元格是可以通过的，此处有一个硬币。

起初，$Bob$ 控制的机器人最初在单元格 $(X,Y)$ 中。他给机器人输入字符串 $T$ ，指挥机器人去捡硬币。

• 假设 $|T|$ 是字符串 $T$ 的长度。对于 $i=1,2,\ldots,|T|$ ，机器人将按照如下规则移动：
  • 假设 $(x,y)$ 是他当前所在的单元格。
    • 如果 $T_i$ 是 U 且 $(x-1,y)$ 单元格可以通过，则移动到 $(x-1,y)$ 单元格。
    • 如果 $T_i$ 为 D 且 $(x+1,y)$ 格可以通过，请移至 $(x+1,y)$ 格。
    • 如果 $T_i$ 为 L 且 $(x,y-1)$ 格可以通过，请移动到 $(x,y-1)$ 格。
    • 如果 $T_i$ 是 R 且 $(x,y+1)$ 单元格可以通过，则移动到 $(x,y+1)$ 单元格。
    • 否则，停留在 $(x,y)$ 格。

注意，机器人也不能移到网格外面，经过单元格有硬币，机器人将自动捡起来，硬币被捡走后此单元格可以再次经过，但硬币消失了。

请问机器人最终停留的位置，以及机器人捡到硬币的数量。

输入格式

输入格式如下：

$H$ $W$ $X$ $Y$

$S_{1,1}S_{1,2}\ldots S_{1,W}$

$\dots$

$S_{H,1}S_{H,2}\ldots S_{H,W}$

$T$

输出格式

三个整数

$X$ $Y$ $C$

其中 $(X,Y)$ 是机器人最终停留的单元格， $C$ 是机器人捡到的硬币数量，$3$ 个整数用空格分隔。

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

2 3 1

样例 1 解释

机器人的行为如下

• $T_1=$ L，所以机器人从 $(3,4)$ 移动到 $(3,3)$ 。捡到一个硬币。
• $T_2=$ L，所以机器人从 $(3,3)$ 移动到 $(3,2)$ 。
• $T_3=$ L，但是 $(3,1)$ 牢房无法通过，所以他停留在 $(3,2)$ 。
• $T_4=$ D，所以机器人从 $(3,2)$ 移动到了 $(4,2)$ 。
• $T_5=$ R，所以机器人从 $(4,2)$ 移动到 $(4,3)$ 。
• $T_6=$ U，因此机器人从 $(4,3)$ 移动到 $(3,3)$ 。此处硬币已经被捡走。
• $T_7=$ U，因此机器人从 $(3,3)$ 移动到 $(2,3)$ 。

机器人在移动过程中捡到硬币的数量为 $1$ 。

6 13 4 6
......#......
.@@@@@@@@@@@.
#@@@@@@@@@@@.
.@@@@.@@@@@@.
.@@@@@@@@@@@.
....#..#.....
UURUURLRLUUDDURDURRR

3 11 11

12 35 7 10
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@.................................@
@..........@......................@
@......@................@.........@
@.............@@............@.....@
@...@@........@@....@@............@
@...@@........@@....@@.......@@...@
@....@@......@@......@@....@@.....@
@....@@......@@......@@..@@.......@
@.....@@@@@@@.........@@@.........@
@.................................@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

4 14 1

数据规模与约定

• $3 \leq H,W \leq 100$
• $1 \leq X \leq H$
• $1 \leq Y \leq W$
• 所有给定的数字都是整数。
• 每个 $S_{i,j}$ 都是 #、.、@ 中的一个。
• $S_{X,Y}=$ .
• $T$ 是长度至少为 $1$ 且最多为 $10^4$ 的字符串，由 U、D、L、R 组成。