给定一张 行 列的方格图，我们使用 表示网格中从上往下数第 行和从左往右数第 列的单元格。每个方格要么是可以通过的空方格（使用 表示），要么是不可通过的墙方格（使用 表示），你可以沿着空方格上下左右随意移动：从 向上移动一格即抵达 、向下移动一格即抵达 、向左移动一格即抵达 、向右移动一格即抵达 ，但是不能移动到墙方格上或者移动出地图。

第 秒时我们在起点 放上一个机器人，这个机器人会按照一个长度为 的行进指令串 进行移动，每个指令为 、、、 的某一个，依次代表向上、下、左、右移动。机器人在第 秒时接受到的指令为 。

你可以控制这个机器人行进，具体来说，对于每一秒，你可以从以下三种操作中选择一种执行（不论执行哪种操作，都算用去 秒，指令序号也随时间前移，即若当前时刻为 ，在本秒结束后进入时刻 ）：
让当前机器人按照当前指令方向进行一步移动；
让当前机器人在原地停留一秒；
忽略当前指令，手动将机器人向 、、、 的某个方向进行一次移动。

你的目标是将机器人移动至终点 （当然，任何时候都不能移动到障碍上或者移动出地图）。现在询问：
最少需要进行多少次手动移动才能够使得机器人可以从 走到 ；
在最小化手动移动次数的前提下，最早在什么时候能够移动到 。
保证起点和终点一定为空方格，你始终可以通过以上操作找到一条从起点出发到达终点的可行路径。

第一行输入两个整数 ，表示地图的行数、列数。
第二行输入一个长度为 ，仅由 、、、 组成的字符串 ，表示机器人的行进指令。
此后  行，第  行输入一个长度为 ，仅由  和  组成的字符串 ，表示地图第  行的状态。

在一行上输出两个整数，表示答案。

5 6
DDDLDUUDLLL
.#..#.
..#...
#...#.
..#...
....#.

5 12

在这个样例中，其中一种可能的最优走法如下（其中字符  分别代表机器人第 0~12 秒所在的位置，如果停在原地则多个字符只保留最早出现的字符）：

上面每秒的操作逻辑为 ，其中  表示停在原地。

6 5
UUDRRDDRRDL
...#.
.#...
...#.
.#...
..#.#
#....

0 19