题目描述

给定一个 $H$ 行 $W$ 列的网格。记从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子为 $(i, j)$。

网格中格子的状态由字符 $C_{i,j}$ 表示：如果 $C_{i,j}$ 为 .，则该格子为空地；如果 $C_{i,j}$ 为 #，则该格子为障碍物。

高桥君目前位于格子 $(S_i, S_j)$，他将按照字符串 $X$ 中的字符顺序，依次执行以下规则的移动（共 $|X|$ 次）：

• 若当前字符为 L，且当前格子左侧存在格子且为空地，则移动到左侧格子；否则留在当前格子。
• 若当前字符为 R，且当前格子右侧存在格子且为空地，则移动到右侧格子；否则留在当前格子。
• 若当前字符为 U，且当前格子上方存在格子且为空地，则移动到上方格子；否则留在当前格子。
• 若当前字符为 D，且当前格子下方存在格子且为空地，则移动到下方格子；否则留在当前格子。

请输出高桥君执行完所有动作后所在的格子坐标。

输入格式

第一行包含两个正整数 $H, W$ —— 表示网格的行数和列数。

第二行包含两个正整数 $S_i, S_j$ —— 表示高桥君的初始位置。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，表示网格的状态。

最后一行包含一个长度在 $1$ 到 $50$ 之间的字符串 $X$ —— 表示动作序列。

输出格式

输出两个整数 $x$ 和 $y$，中间用空格隔开，表示高桥君最终所在的格子坐标 $(x, y)$。

样例输入 1

2 3
2 1
.#.
...
ULDRU

样例输出 1

2 2

样例输入 2

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

样例输出 2

2 4

样例输入 3

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

样例输出 3

1 1

说明

样例解释

在第一个样例中，高桥君起始位置为 $(2, 1)$，动作序列执行过程如下：

• 第 $1$ 个字符 U，上方存在空格子 $(1, 1)$，移动到 $(1, 1)$。
• 第 $2$ 个字符 L，左侧不存在格子，留在 $(1, 1)$。
• 第 $3$ 个字符 D，下方存在空格子 $(2, 1)$，移动到 $(2, 1)$。
• 第 $4$ 个字符 R，右侧存在空格子 $(2, 2)$，移动到 $(2, 2)$。
• 第 $5$ 个字符 U，上方存在格子但不是空地，留在 $(2, 2)$。 最终高桥君位于 $(2, 2)$。

数据范围

对于所有测试点，保证 ：

• $1 \le H, W \le 50$，
• $1 \le S_i \le H, 1 \le S_j \le W$，
• 保证 $C_{S_i, S_j} =$ .。
• 保证 $X$ 是一个长度在 $1$ 到 $50$ 之间的字符串，仅由 L, R, U, D 组成。
• 保证所有的输入值均为整数。