教授再次失去了他的家用机器人。经过一番思考,教授明白他把机器人留在了地下室。
教授家的地下室由一个 n × m 的矩形表示,分为 1 × 1 的正方形。有些广场是无法逾越的围墙;其他广场还可以。您可以通过边缘相邻的可通行方块从任何可通行方块到达任何其他可通行方块。一个可通行的广场是地下室的出口。机器人恰好放置在一个可通行的方格内。机器人也可以放置在出口广场。
教授害怕晚上去黑暗的地下室寻找机器人。不过,他有一个地下室平面图和机器人的遥控器。使用遥控器,教授可以向机器人发送信号,以向左、向右、向上或向下移动一个方块。当机器人接收到信号时,如果机器人在给定方向上的相邻方格可以通过,则它会向所需的方向移动。否则,机器人将保持空闲状态。
教授在一张纸上写下了一系列 k 个命令。他认为这个序列可以引导机器人走出地下室,无论它的初始位置在哪里。教授对另一个机器人进行了编程,使其根据纸上的注释按下遥控器上所需的按钮。教授正要运行程序并上床睡觉,这时他顿悟了。
执行每个命令都需要一些能量,教授不希望在月底收到巨额电费。这就是为什么他想在他写出的序列中找到最小可能的前缀,以保证在前缀满足后引导机器人到达出口。这就是教授在这么晚的时候向你提出的问题。
输入
第一行包含三个整数 n、m 和 k (3 ≤ n, m ≤ 150, 1 ≤ k ≤ 105)。接下来的n行每行包含m个字符——这是教授的地下室的描述:“#”代表一堵墙,“.”代表一堵墙。代表可通行的广场,“E”代表地下室的出口(该广场也是可通行的)。从每个可通行的方格都可以到达出口,位于 n × m 矩形周长的所有方格都是墙。正好一格就是地下室的出口。最后一行包含 k 个字符,是教授在纸上写下的命令序列的描述。 “L”、“R”、“U”、“D”分别代表左、右、上、下命令。
输出
在输出文件中打印将引导机器人到达出口广场的最小可能前缀的长度。换句话说,无论机器人最初定位在哪里,在前缀中的所有命令都得到满足后,它应该定位在出口广场上(在执行命令期间,机器人可以来回离开出口广场,但只有机器人的最后一个位置对我们来说是有趣的)。如果教授错了并且没有前缀(包括整个序列)可以将机器人带到出口,则打印“-1”(不带引号)。如果存在唯一可通过的方块并且它是出口,则打印“0”(不带引号)。
示例
输入 #1
5 5 7 ##### #...# #...# #E..# ##### UULLDDR
输出 #1
6
输入 #2
5 5 7 ##### #.#.# #...# #E..# ##### UULLDDR
输出 #2
-1
输入 #3
5 3 2 ### #.# #.# #E# ### DD
输出 #3
2