题目描述

小 Z 有一个 $n$ 行 $m$ 列的矩形场地。场地中每个格子要么是空地，要么是障碍物。我们用字符 $\tt{.}$ 表示空地，用字符 $\tt{\#}$ 表示障碍物。

场地中有一台巡逻机器人，初始时它位于第 $r$ 行第 $c$ 列（行、列均从 $1$ 开始编号），朝向为东（即"向右"）。

机器人会依次执行一条长度为 $L$ 的指令串，指令串只由 $\tt F$、$\tt L$、$\tt R$ 三种字符组成，含义如下：

• $\tt F$：尝试向前移动一格。如果机器人前方一格仍在场地内，并且那个格子是空地，机器人就移动到该格；否则机器人停留在原地，并且这一次"受阻"会被记录下来。
• $\tt L$：原地向左转 $90$ 度。不移动，也不计受阻。
• $\tt R$：原地向右转 $90$ 度。不移动，也不计受阻。

请你求出：全部指令执行完之后，机器人所在的行号、列号，以及整个过程中"受阻"的总次数。

输入格式

第一行包含三个整数 $n,m,L$，分别表示场地的行数、列数和指令串的长度。

第二行包含两个整数 $r,c$，表示机器人的初始位置。

接下来 $n$ 行，每行一个长度为 $m$ 的、仅由 $\tt{.}$ 和 $\tt{\#}$ 组成的字符串，描述场地。保证第 $r$ 行第 $c$ 个字符是 $\tt{.}$。

最后一行包含一个长度为 $L$ 的、仅由 $\tt F$、$\tt L$、$\tt R$ 组成的字符串，表示指令串。

输出格式

输出一行三个整数，依次表示机器人最终所在的行号、列号和受阻的总次数，相邻两个整数之间用一个空格隔开。

3 4 6
1 1
....
....
....
FFRFFR

3 3 0

3 3 8
2 2
...
.#.
...
FFRFFLFF

3 3 4

数据范围与提示

【样例 1 解释】

初始时机器人在第 $1$ 行第 $1$ 列，朝东。

• $\tt F$：向东移动到 $(1,2)$；
• $\tt F$：向东移动到 $(1,3)$；
• $\tt R$：原地转向，朝南；
• $\tt F$：向南移动到 $(2,3)$；
• $\tt F$：向南移动到 $(3,3)$；
• $\tt R$：原地转向，朝西。

全程没有受阻，最终位于第 $3$ 行第 $3$ 列，故输出 $\tt{3\ 3\ 0}$。

【样例 2 解释】

初始时机器人在第 $2$ 行第 $2$ 列，朝东。

指令	说明	受阻次数
$\tt F$	向东移动到 $(2,3)$	$0$
	向东要到 $(2,4)$，超出场地，留在原地	$1$
$\tt R$	转向，朝南
$\tt F$	向南移动到 $(3,3)$
	向南要到 $(4,3)$，超出场地，留在原地	$2$
$\tt L$	转向，朝东
$\tt F$	向东超出场地，留在原地	$3$
		$4$

最终位于第 $3$ 行第 $3$ 列，共受阻 $4$ 次，故输出 $\tt{3\ 3\ 4}$。

【数据范围】

对于所有测试数据，保证：

• $1 \le n,m \le 1000$；
• $1 \le L \le 10^6$；
• $1 \le r \le n$，$1 \le c \le m$，且第 $r$ 行第 $c$ 个字符为 $\tt{.}$；
• 指令串中只包含 $\tt F$、$\tt L$、$\tt R$ 三种字符。

测试点编号	$n \le$	$m \le$	$L \le$	特殊性质
$1$	$1$	$1$	$10$	无
$2$		$5$	$30$
$3$	$5$	$1$
$4$	$3$		$60$
$5$	$10$		$10^3$	A
$6\sim 8$				无
$9\sim 10$	$50$		$2 \times 10^4$
$11\sim 12$	$100$		$10^5$
$13\sim 14$	$500$		$5 \times 10^5$
$15$	$1000$	$1000$	$10^6$	A
$16\sim 17$				无
$18$		$1$		A
$19$	$1$	$1000$
$20$	$1000$

特殊性质 A：场地中不存在障碍物。