Background

Hack testdata sets #11 and #12 were provided by uid=20285.

OIers dream (Konpaku Youmu) of visiting Gensokyo. This time, while they were sleeping (Komeiji), they traveled to Gensokyo in a dream. There are many (ju) girls (ruo) in Gensokyo, but they were attracted by the beauty of the (old lady) girls (and the delicious konnyaku), and got lost in Gensokyo.

Brave (dead otaku) boy, now you have a map of the Human Village in Gensokyo in your hand. You know the OIers' position, and you can remotely send information to them. Please guide the lost OIers to the altar that leads them back to real life.

Problem Description

You are given an $N \times M$ map, as shown below:

5400000S01     
1111101101     
000003X301      
3111111101     
E000300031      
1111X30001     

There are many strange things on it:

• $S$ is the starting point, and $E$ is the destination.
• $0$ is empty ground. You can walk as you like, and moving one cell costs $1s$.
• $1$ is a wall, which you cannot pass through (unless you are blessed by the Wind God Girl).
• $2$ is a small youkai. You need $3s$ to defeat it before you can pass through this cell. (PS: After being defeated, the youkai revives immediately once you leave the current cell.)
• $3$ is a big youkai. You need $8s$ to defeat it before you can pass through this cell.
• $4$ is the Sunflower Field. When you arrive here, you can obtain a sunflower. After obtaining it, when you meet a youkai, you can pass through the youkai's cell directly.
• $5$ is the Roukanken (Trivia: Roukanken, English name $Louguan\ is\ very\ jian$, is a sword forged by youkai; there is almost nothing it cannot cut). When you arrive here, you may spend $5s$ to obtain it. After obtaining it, you can cut walls and youkai, turning them into empty ground (you may also choose not to cut them). Cutting walls and youkai costs no time. Roukanken can be used indefinitely and will not break. With Roukanken, you can still use gaps, but Roukanken cannot cut gaps (or the completely useless mochi; mochi Youmu UUZ is one family anyway).
• $M$ is mochi (it is $mashu$, not $mafu$ if you do not know what mochi is, I will cut you with Roukanken). After you touch mochi, you can eat it. (Passerby A: Then why did you add this thing? Setter: If there is $S$, there must be $M$. Passerby B: I'd rather die outside, or jump down into a gap, than eat mochi! Hmm, smells good!)
• $X$ is Yukari's gap. After you touch a gap, you will be teleported to any other gap. (The testdata does not guarantee there are only 0 or 2 gaps; that is, there may be many gaps and you can teleport randomly.) Each teleport costs $1s$. (When passing through the current cell, you may also choose not to use the gap.)

Output the minimum time needed for the OIers to reach the destination. If it is impossible, output "We want to live in the TouHou World forever".

Translation: No regrets entering Touhou in this life; in the next life, sleep with everyone I wish to be born in Gensokyo.

Warm reminder: It is possible that the optimal path has weird moves such as going back.

Input Format

There are $N + 1$ lines in total.

Line $1$ contains $N$ and $M$. Lines $2$ to $N + 1$ contain the $N \times M$ map.

Output Format

One line: the minimum time, or "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

Hint

For $30\%$ of the testdata, $1 \leq N, M \leq 50$. For $50\%$ of the testdata, $1 \leq N, M \leq 100$. For $100\%$ of the testdata, $1 \leq N, M \leq 1000$.

It is guaranteed that there is one testdata set whose answer is "We want to live in the TouHou World forever". The testdata has graded difficulty.

Sample Explanation

Sample 1: Reach Roukanken at $7s$, obtain Roukanken at $12s$, then cut downward all the way to reach the destination. Sample 2: Reach $(3,3)$ at $10s$, reach $(3,10)$ at $32s$, go upward into a gap and then reach the destination. Sample 3: No need to explain this one (the setter totally went wild).

Translated by ChatGPT 5