103641: [Atcoder]ABC364 B - Grid Walk

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.

Cell $(i, j)$ is empty if $C_{i, j}$ is ., and not empty if $C_{i, j}$ is #.

Takahashi is currently at cell $(S_i, S_j)$, and he will act according to the following rules for $i = 1, 2, \ldots, |X|$ in order.

• If the $i$-th character of $X$ is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
• If the $i$-th character of $X$ is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
• If the $i$-th character of $X$ is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
• If the $i$-th character of $X$ is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

• $1 \leq H, W \leq 50$
• $1 \leq S_i \leq H$
• $1 \leq S_j \leq W$
• $H, W, S_i, S_j$ are integers.
• $C_{i, j}$ is . or #.
• $C_{S_i, S_j} =$ .
• $X$ is a string of length between $1$ and $50$, inclusive, consisting of L, R, U, D.

Input

The input is given from Standard Input in the following format:

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

Output

Let $(x, y)$ be the cell where Takahashi is after completing the series of actions. Print $x$ and $y$, separated by a space.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell $(2, 1)$. His series of actions are as follows:

• The 1st character of $X$ is U, and the cell above $(2, 1)$ exists and is an empty cell, so he moves to the cell above, which is $(1, 1)$.
• The 2nd character of $X$ is L, and the cell to the left of $(1, 1)$ does not exist, so he stays at $(1, 1)$.
• The 3rd character of $X$ is D, and the cell below $(1, 1)$ exists and is an empty cell, so he moves to the cell below, which is $(2, 1)$.
• The 4th character of $X$ is R, and the cell to the right of $(2, 1)$ exists and is an empty cell, so he moves to the cell to the right, which is $(2, 2)$.
• The 5th character of $X$ is U, and the cell above $(2, 2)$ exists but is not an empty cell, so he stays at $(2, 2)$.

Therefore, after completing the series of actions, he is at cell $(2, 2)$.

Sample Input 2

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

Sample Output 2

2 4

Sample Input 3

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

Sample Output 3

1 1

问题陈述

有一个有$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，并且他当前单元格下方的单元格存在且为空，则他移动到下方的单元格。否则，他保持在当前单元格。

打印他完成一系列动作后的单元格位置。

约束条件

• $1 \leq H, W \leq 50$
• $1 \leq S_i \leq H$
• $1 \leq S_j \leq W$
• $H, W, S_i, S_j$都是整数。
• $C_{i, j}$是.或#。
• $C_{S_i, S_j} =$ .
• $X$是一个长度在$1$到$50$之间（包含）的字符串，由L、R、U、D组成。

输入

输入从标准输入以下格式给出：

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

输出

设$(x, y)$是高桥完成一系列动作后的单元格位置。打印$x$和$y$，用空格分隔。

样本输入1

2 3
2 1
.#.
...
ULDRU

样本输出1

2 2