rt和zx跑毒圈终于来到了决赛圈，敌人突然盲扔一个燃烧瓶，
rt和zx每秒都可以上下左右移动。
火势每秒快速的向周围八个格子（上下左右、左上、右上、左下、右下）蔓延，
敌人暴露了位置，两人想快速找到敌人并击杀，毒圈可以看成是一个n*m的地图，在图中有：
“-”:空地，可走。
“|”：一个不可翻越的山，火可以在上边蔓延。
“.”：rt和zx所在地方。
“o”：敌人的地方。
“!”：燃烧瓶位置。
判断两人能否成功杀掉敌人，若可以，输出击杀敌人的最短时间，否则输出die。

第一行输入两个整数n，m，表示毒圈的大小。
接下来n行，每行m个字符，表示此地图。
3<=n<=30
3<=m<=30

每组数据输出一行，如果两人能够成功到达出口，输出击杀敌人的最短时间，否则输出die。

示例输入
5 5
---|!
--|.|
---||
----o
-----
输出
die

2021级ACM集训队选拔赛（6）