题目描述

给定一个 $H$ 行 $W$ 列的网格。# 表示墙，. 表示可通行空地，@ 表示可通行且有房子。

圣诞老人初始在 $(X,Y)$。他按字符串 $T$ 的字符依次移动，U,D,L,R 分别表示向上、下、左、右走一格。如果目标格可通行则移动，否则原地不动。

求最终位置，以及他经过或到达过的不同房子数量。重复经过同一房子只计一次。

输入格式

第一行输入 $H,W,X,Y$。

接下来 $H$ 行输入网格。

最后一行输入字符串 $T$。

输出格式

输出最终行号、列号和经过的不同房子数量。

样例

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

2 3 1

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

3 11 11

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

4 14 1

样例说明

在样例 $1$ 中，圣诞老人按照指令移动后停在第 $2$ 行第 $3$ 列，途中到达过 $1$ 座不同的房子。

在样例 $2$ 中，最终位置为 $(3,11)$，一共到达过 $11$ 座不同的房子。重复经过同一座房子不会重复计数。

在样例 $3$ 中，最终位置为 $(4,14)$，途中到达过 $1$ 座房子。

数据范围

$3\le H,W\le100$，$1\le X\le H$，$1\le Y\le W$。边界格均为 #，$S_{X,Y}$ 为 .。$1\le |T|\le10^4$。