$\text{ZEH}$ 和 $\text{YYR}$ 到一个洞穴探险，其中 $\text{YYR}$ 进入洞穴探险，而 $\text{ZEH}$ 在洞外附近利用自发研制的X-1探测器监测洞穴的喷气口是否开始喷射毒气。

洞穴里面有若干个毒气喷射口，已知毒气的扩散速度是每单位时间向上下左右扩散一格，而 $\text{YYR}$ 的逃逸速度也是每单位时间向上下左右移动一格。所有的毒气喷射口都是同时喷发的，当监测到喷射时， $\text{ZEH}$ 就马上通知 $\text{YYR}$ 逃离， $\text{YYR}$ 必须在不遇到毒气的情况下尽快逃离洞穴。亲爱的师弟师妹，你们可以帮他们计算一下 $\text{YYR}$ 最快逃离洞穴的时间吗？

输入格式

洞穴地图用矩阵表示，符号. 表示通路，符号 X 表示障碍物，符号 E 表示洞口，符号 D 表示毒气喷射口所在地，符号 P 表示 $\text{YYR}$ 当前的位置。

输入首先是两个整数 $m$ , $n$ ( $2\le m,n\le 1000$ )表示矩阵的大小。

接下来是 $m$ 行 $n$ 列的矩阵图。矩阵描述之外的地方都是障碍物且只有一个逃离的洞口，但可能有多个毒气喷射口，且扩散到洞口的毒气立即消散。

输入有多组数据，当 $m,n$ 是 $0,0$ 时表示输入结束。

输出格式

如果 $\text{YYR}$ 能够顺利逃离洞穴，则输出最快逃离洞口的时间，否则输出“YYR is extremely dangerous!”

样例

样例输入

5 10
XXXXX..XXX
XXXE...XXX
XX.......X
X......P.X
XD.....XXX
5 10
XXXXX..XXX
XXXE...XXX
XX.......X
X......P.X
X.D....XXX
0 0

样例输出

6
YYR is extremely dangerous!

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$65536\mathrm{KB}$