该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

文件输入输出提示

本题采用文件输入输出。提交代码时，请在 main 函数开头加入文件重定向，并从 patrol.in 读入、输出到 patrol.out。

freopen("patrol.in", "r", stdin);
freopen("patrol.out", "w", stdout);

题目描述

苗苗正在调试一辆校园机房巡检小车。机房被划分为 $H$ 行 $W$ 列的网格。每个格子要么可以通行，要么是障碍。

一辆巡检小车从给定位置出发，按顺序尝试执行一串移动指令。每条指令是下面四种字符之一：

• U：向上移动一格；
• D：向下移动一格；
• L：向左移动一格；
• R：向右移动一格。

对每条指令：

• 如果目标格在网格内，且不是障碍，小车就移动过去。
• 否则，这条指令被忽略，小车留在原地。

请输出所有指令执行结束后小车的位置，以及一共有多少条指令被忽略。

输入格式

从文件 patrol.in 中读入数据。

第一行输入两个整数 $H,W$。

第二行输入两个整数 $r,c$，表示小车初始位于第 $r$ 行第 $c$ 列。行和列均从 $1$ 开始编号。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串，表示网格。字符 . 表示可以通行，字符 # 表示障碍。

最后一行输入一个字符串 $s$，表示移动指令。

输出格式

输出到文件 patrol.out 中。

输出一行三个整数，分别表示小车最终所在的行号、列号和被忽略的指令数量。

输入输出样例 #1

输入 #1

5 6
2 2
......
..#...
......
.#....
......
RRDDLLUU

输出 #1

1 1 4

说明/提示

前两条 R 指令都会尝试走到障碍格，因此被忽略。

之后小车向下走到第 3 行第 2 列，再尝试向下走到第 4 行第 2 列时遇到障碍，该指令也被忽略。

接着小车向左走到第 3 行第 1 列，再继续向左会走出网格，该指令被忽略。

最终小车停在第 1 行第 1 列，共有 4 条指令被忽略。

输入输出样例 #2

输入 #2

3 3
1 1
...
...
...
RRDDLLUU

输出 #2

1 1 0

数据范围与子任务

对于所有数据，满足：

• $1\le H,W\le 1000$；
• $H\times W\le 10^6$；
• 初始位置一定不是障碍；
• $1\le \lvert s\rvert\le 2\times 10^5$；
• $s$ 仅由字符 U、D、L、R 组成。

patrol_大样例.zip