Score : $200$ points

问题陈述

有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示从顶部数第 $i$ 行，从左边数第 $j$ 列的单元格。

如果 $C_{i, j}$ 是 .，则单元格 $(i, j)$ 是空的；如果 $C_{i, j}$ 是 #，则单元格不为空。

高桥目前位于单元格 $(S_i, S_j)$，他将按照以下规则进行操作，对于 $i = 1, 2, \ldots, |X|$ 依次执行。

• 如果 $X$ 的第 $i$ 个字符是 L，并且他当前单元格左侧的单元格存在且为空，则他向左移动到该单元格。否则，他留在当前单元格。
• 如果 $X$ 的第 $i$ 个字符是 R，并且他当前单元格右侧的单元格存在且为空，则他向右移动到该单元格。否则，他留在当前单元格。
• 如果 $X$ 的第 $i$ 个字符是 U，并且他当前单元格上方的单元格存在且为空，则他向上移动到该单元格。否则，他留在当前单元格。
• 如果 $X$ 的第 $i$ 个字符是 D，并且他当前单元格下方的单元格存在且为空，则他向下移动到该单元格。否则，他留在当前单元格。

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

以上为大语言模型 kimi 翻译，仅供参考。

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