网格行走

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

当 $C_{i, j}$ 为 . 时,格子 $(i, j)$ 是空的;当 $C_{i, j}$ 为 # 时,格子 $(i, j)$ 不是空的。

高桥君现在位于格子 $(S_i, S_j)$,他按照以下规则,按顺序执行 $i = 1, 2, \ldots, |X|$ 次行动。

• 如果 $X$ 的第 $i$ 个字符是 L,且当前格子左边的格子存在且为空,他移动到左边的格子。否则,他停留在当前格子。
• 如果 $X$ 的第 $i$ 个字符是 R,且当前格子右边的格子存在且为空,他移动到右边的格子。否则,他停留在当前格子。
• 如果 $X$ 的第 $i$ 个字符是 U,且当前格子上方的格子存在且为空,他移动到上方的格子。否则,他停留在当前格子。
• 如果 $X$ 的第 $i$ 个字符是 D,且当前格子下方的格子存在且为空,他移动到下方的格子。否则,他停留在当前格子。

输出完成所有行动后他所处的格子。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$
$S_i$ $S_j$
$C_{1, 1} \ldots C_{1, W}$
$\vdots$
$C_{H, 1} \ldots C_{H, W}$
$X$

输出格式

设完成所有行动后高桥君所处的格子为 $(x, y)$。输出 $x$ 和 $y$,以空格分隔。

样例

2 3
2 1
.#.
...
ULDRU

2 2

高桥君从格子 $(2, 1)$ 出发。他的行动序列如下：

$X$ 的第 1 个字符是 U,$(2, 1)$ 上方的格子存在且为空,所以他移动到上方的格子 $(1, 1)$。

$X$ 的第 2 个字符是 L,$(1, 1)$ 左边的格子不存在,所以他停留在 $(1, 1)$。

$X$ 的第 3 个字符是 D,$(1, 1)$ 下方的格子存在且为空,所以他移动到下方的格子 $(2, 1)$。

$X$ 的第 4 个字符是 R,$(2, 1)$ 右边的格子存在且为空,所以他移动到右边的格子 $(2, 2)$。

$X$ 的第 5 个字符是 U,$(2, 2)$ 上方的格子存在但不是空,所以他停留在 $(2, 2)$。

因此,完成所有行动后,他位于格子 $(2, 2)$。

4 4
4 2
....
.#..
...#
....
DUUUURULRD

2 4

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

1 1

数据范围

• $1 \le H, W \le 50$
• $1 \le S_i \le H$
• $1 \le S_j \le W$
• $H, W, S_i, S_j$ 是整数
• $C_{i, j}$ 是 . 或 #
• $C_{S_i, S_j} =$ .
• $X$ 是由 L、R、U、D 组成的字符串,长度在 $1$ 到 $50$ 之间