OIer们的东方梦
题目背景
**#11,#12 两组 Hack 数据由 uid=20285 提供**
OIer 们做~~魂魄妖~~梦都想去幻想乡玩一下。这一次，他们在睡~~古明地~~觉时在梦中穿越去了幻想乡，幻想乡有很多的少(ju)女(ruo)，但是他们被~~老太婆~~少女的美色~~和蒟蒻的美味~~所吸引，在幻想乡中迷失了方向。
勇敢的~~死肥宅~~少年啊，现在你手里有一份幻想乡人间之里的地图，你知道 OIer 们的位置，你可以远程给OIer们传递信息，请你带领迷路的 OIer 们走进回到现实生活的祭坛吧！
题目描述
给你一个 $N\times M$ 的地图，如图所示：
```
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001
```
其中有很多稀奇古怪的东西：
* $S$ 表示出发点，$E$ 表示终点。
* $0$ 表示空地，你想怎么走就怎么走，走一格需要 $1s$。
* $1$ 表示墙，你无法通行（~~除非你受到了**风神少女**的庇护~~）。
* $2$ 表示小妖怪，你需要 $3s$ 的时间去消灭小妖怪，才能经过该位置。（PS: 妖怪被消灭后只要离开当前格子立刻复活）
* $3$ 表示大妖怪，你需要 $8s$ 的时间去消灭大妖怪，才能经过该位置。
* $4$ 表示太阳花田，到达该位置可以获得太阳花，获得太阳花后遇到妖怪时可**直接**通过该妖怪的位置。
* $5$ 表示楼观剑（科普君：楼观剑，英文名 $Louguan\ is\ very\ jian$，是妖怪做的剑，楼观剑斩不断的东西几乎没有)，到达该位置可以花费 $5s$ 获得它，获得它后可以砍墙砍妖怪将其变成空地（当然也可以不砍，砍墙砍妖怪不需要时间，楼观剑可以一直使用**不会损坏**，有了楼观剑依然可以使用隙间，但是楼观剑不能砍隙间~~和一点用都没有的麻薯，麻薯妖梦UUZ是一家嘛~~）
* $M$ 表示麻薯（是 $mashu$ 不是 $mafu$~~不知道麻薯是什么的一把楼观剑给你砍过来~~)，碰到麻薯后你可以把它吃了(路人甲：那你为什么还要加这个东西? 出题人：有 $S$ 肯定要有 $M$ 啊。路人乙：我就是死外边，从隙间中跳下去，也不会吃麻薯！嗯~真香！）
* $X$ 表示紫妈的隙间，碰到隙间后会传送至其他的任意一个隙间(数据**不**保证只有 0 或 2 个隙间，**就是说可以有很多隙间乱传**)，每次传送耗时 $1s$。(经过当前格子时可以不经过隙间)
答案输出 OIer 们到达终点所需最短时间。如果无法到达，输出 "We want to live in the TouHou World forever"。
翻译：此生无悔入东方，来世~~睡遍~~愿生幻想乡。
**温馨提示：不排除存在可以往回走等稀奇古怪的最优走法**
输入输出格式
输入格式
数据共有 $N+1$行。
第 $1$ 行输入 $N$ 和 $M$。
第 $2$ 到 $N+1$ 行输入 $N\times M$ 的地图。
输出格式
一行，最短时间或者 "We want to live in the TouHou World forever"。
输入输出样例
输入样例 #1
6 10
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001输出样例 #1
16输入样例 #2
5 10
S23323323X
2032332333
1202202202
1111111111
11111111XE输出样例 #2
44输入样例 #3
9 10
SX1X0X1X1X
2332332333
5205205200
XXXXXXXXXX
2222222222
3333333333
3333333333
XXXXXXXXXX
XXXXXXXXXE输出样例 #3
3说明
对于 $30\%$ 的数据，$1\leq N,M\leq 50$。
对于 $50\%$ 的数据，$1\leq N,M\leq 100$。
对于 $100\%$ 的数据，$1\leq N,M\leq 1000$。
保证有一组数据答案为 "We want to live in the TouHou World forever"，数据有梯度。
### 样例解释
**样例 1**：在 $7s$ 时到达楼观剑，在 $12s$ 时获得楼观剑，一路向下砍到达终点。
**样例 2**：在 $10s$ 时到达 $(3,3)$，在 $32s$ 时到达$(3,10)$，向上进入隙间后到达终点。
**样例 3**：这个就不用解释了吧(出题人放飞自我)。