题目描述

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

如果 $S_{i,j}$ 是 #，则该格子不可通行；如果是 .，则该格子可通行且没有房子；如果是 @，则该格子可通行且包含一个房子。

最初，圣诞老人位于格子 $(X,Y)$。他将根据字符串 $T$ 采取如下行动：

设 $|T|$ 为字符串 $T$ 的长度。对于 $i = 1, 2, \dots, |T|$，他按以下规则进行移动： 设他当前所在的格子为 $(x, y)$。

• 若 $T_i$ 是 U，且格子 $(x-1, y)$ 可通行，则移动到格子 $(x-1, y)$。
• 若 $T_i$ 是 D，且格子 $(x+1, y)$ 可通行，则移动到格子 $(x+1, y)$。
• 若 $T_i$ 是 L，且格子 $(x, y-1)$ 可通行，则移动到格子 $(x, y-1)$。
• 若 $T_i$ 是 R，且格子 $(x, y+1)$ 可通行，则移动到格子 $(x, y+1)$。
• 否则，留在当前格子 $(x, y)$。

请找出他完成所有行动后所在的格子，以及他在行动期间经过或到达的不同房子的数量。如果同一个房子被经过多次，只计算一次。

输入格式

第一行包含四个整数 $H, W, X, Y$。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串。其中第 $i$ 行的第 $j$ 个字符 $S_{i,j}$ 表示格子 $(i,j)$ 的状态。

最后一行包含一个字符串 $T$。

输出格式

设完成所有行动后他所在的格子为 $(X', Y')$，以及他在行动期间经过或到达的不同房子的数量为 $C$。请在一行中依次输出 $X', Y', C$，相邻数字之间用一个空格隔开。

样例输入 1

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

样例输出 1

2 3 1

样例输入 2

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

样例输出 2

3 11 11

样例输入 3

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

样例输出 3

4 14 1

说明

样例解释

在第一个样例中，圣诞老人的行动如下：

• $T_1 = \text{L}$，所以他从 $(3,4)$ 移动到 $(3,3)$。经过了一个房子。
• $T_2 = \text{L}$，所以他从 $(3,3)$ 移动到 $(3,2)$。
• $T_3 = \text{L}$，但是格子 $(3,1)$ 不可通行，所以他停留在 $(3,2)$。
• $T_4 = \text{D}$，所以他从 $(3,2)$ 移动到 $(4,2)$。
• $T_5 = \text{R}$，所以他从 $(4,2)$ 移动到 $(4,3)$。
• $T_6 = \text{U}$，所以他从 $(4,3)$ 移动到 $(3,3)$。经过了一个房子，但这间房子之前已经被经过了。
• $T_7 = \text{U}$，所以他从 $(3,3)$ 移动到 $(2,3)$。

他在行动期间经过或到达的不同房子数量为 $1$。

数据范围

• 对于所有测试点，保证 $3 \le H, W \le 100$。
• 保证 $1 \le X \le H$，$1 \le Y \le W$。
• 保证 $S_{i,j}$ 均是 #, ., @ 之一。
• 保证网格的四周边界完全是 #（即对于所有的 $1 \le i \le H$，$S_{i,1}$ 和 $S_{i,W}$ 均为 #；对于所有的 $1 \le j \le W$，$S_{1,j}$ 和 $S_{H,j}$ 均为 #）。
• 保证初始位置为空地，即 $S_{X,Y} =$ .。
• 保证 $T$ 是一个长度在 $1$ 到 $10^4$ 之间，且仅包含 U, D, L, R 的字符串。
• 保证所有的输入数值均为整数。