暂无测试数据。

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

题目背景

喵~

题目描述

猫娘现在被困在了一个被称作“迷宫”的东西里面。迷宫大小 \(n\times m\)，由下列方块构成：

• . ，表示空地，随意走动；
• # ，表示墙壁，不能通过；
• B ，表示起点，即猫娘现在的位置；
• E ，表示迷宫的终点，猫娘要前往这里；

由于这是用来困住猫娘的迷宫，所以逃出去的难度极大。有下列特殊性质：

• T ，这是猎人，如果猫娘被猎人看到，需要额外浪费三秒打败猎人，也就是 \(4\) 秒。 如果此时有多个猎人可以看到，则立即失败。 猎人的观察能力很菜，只能观察到上下左右两个的范围。也就是如图的范围，可以穿透墙壁（？）。猎人死亡后会重新在原地生成。
• Y ：这是一种神奇的监控，猫娘不能在此处停留，但可以经过。即这一秒进入，下一秒必须出去。
• W ：这里的地形很奇妙：初始为墙，一秒后变为空地，再一秒变为墙......

不碰到墙的标准：本次进入的点是空地或 B E T Y 。

..#..
..#..
#####
..#..
..#..

猫娘有一个可以使用 \(k\) 次的技能：跳跃：一次性向一个方向移动两格。可以跳过墙（不然叫什么技能啊）

猫娘每次可以选择：移动、跳跃、不动。

问猫娘逃出去的时间为多少？

输入格式

第一行三个整数 \(n,m,k\)。

接下来 \(n\) 行，每行 \(m\) 个字符。

输出格式

输出猫娘逃出去的时间。如果无法逃出，输出 Miao~。

样例输入 #1

7 5 0
B####
.....
#.##.
..#..
#.#.#
#.#E#
#...#

样例输出 #1

10

样例输入 #2

6 6 2
.#B..T
.##..T
.##..T
.##..T
.##..T
.#E..T

样例输出 #2

7

样例解释 #2

很多猎人怎么办？跳过墙就可以了！

样例输入 #3

6 6 2
B.....
#####W
YYYYYY
W####.
.T....
T.T.TE

样例输出 #3

13

样例解释 #3

到了终点被猎人看见了也不行。

数据范围

对于 \(20\%\) 的数据，\(n,m\le 10^3\)。

对于另外 \(10\%\) 的数据，不存在 T ， Y ， W 。

对于另外 \(10\%\) 的数据，不存在 Y ， W 。

对于另外 \(10\%\) 的数据，不存在 W 。

对于另外 \(20\%\) 的数据，\(k=0\)。

对于 \(100\%\) 的数据，\(nm\le 10^6,k\le 5\)，只存在 . ，# ，B ，E， T， Y， W。