题目背景

SuperIke_Liu 、 fire_dragon 、 donke 和 jacky_hu 都爱上了打 死亡代码 。这天，他们约好了一起打疯狂人机，结果他们四个被一个疯狂人机拿下了，这令他们十分不爽，于是他们展开了各自的训练计划。

题目简介

fire_dragon 要苦练舔包，知周所众， fire_dragon 就是喷火龙（宝可梦乱入）的意思，放到了 死亡代码 中就是直升机了，而直升机的来源就是盒子。 fire_dragon 掌握了分别盒子与爆炸诱饵的区别之后就开始练习在最快速度之内拿到直升机。 fire_dragon 的走位分为以下几种：

fire_dragon 向前走（或向后走一步），视为一步。

---

fire_dragon 跳一下，视为一步，如图所示（ # 为地面， @ 为 fire_dragon 原位，* 为位移后的位置）:

!*#
@##
###

---

fire_dragon 向下走一步，视为一步，如图所示:

!@#
*##
###

---

fire_dragon 一个大跳，视为两步，如图所示:

*!@
# #

或

*!!
# @
# #

或

!!@
* #
# #
//这种情况视为一步

\(\large 以上所有移动必须是在用 ! 标出的空格存在时才可以进行！！！\)
\(\large 地图外一圈视为墙\)

---

现在， fire_dragon 给你一个地图，问你他最少需多少步可以到达盒子。

题目数据

第一行两个整数 \(N,M\) ，表示地图长宽。
接下来 \(N\) 行，每行 \(M\) 个字符，若为 * 表示空气，若为 s 表示出发点，若为 e 表示盒子，若为 # 表示地面。

输出到达盒子的最少步数，如果无法到达，输出 died_dragon 。

样例

输入

3 3
**e
**#
#*s

输出

4

尾声

fire_dragon 来到了盒子旁，他激动地打开盒子

他发现这是爆炸诱饵 To Be Continue

请自动脑补音乐