题目背景

#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"。

6 10
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001

16

5 10
S23323323X
2032332333
1202202202
1111111111
11111111XE

44

9 10
SX1X0X1X1X
2332332333
5205205200
XXXXXXXXXX
2222222222
3333333333
3333333333
XXXXXXXXXX
XXXXXXXXXE

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：这个就不用解释了吧(出题人放飞自我)。