Escape the Enchanted Map

You are given an N × M grid map with various types of cells. Your task is to determine the minimum time required to travel from the starting point S to the destination E. If it is impossible to reach the destination, output "We want to live in the TouHou World forever".

The grid contains the following cells:

• S: Starting point.
• E: Destination (end point).
• 0: Open space. Moving into this cell costs 1 second.
• 1: Wall. You cannot pass through unless you have the Louguan Sword (see below).
• 2: Small monster. Without any aid, you must spend 3 seconds to defeat it; however if you have a sunflower or the Louguan Sword, you can pass through in 1 second (without extra combat time).
• 3: Large monster. Without any aid, it costs 8 seconds to defeat it; with a sunflower or the Louguan Sword, the cost is 1 second.
• 4: Sunflower field. Stepping into this cell costs 1 second and grants you a sunflower. With a sunflower, you can pass monsters directly (i.e. in 1 second) without spending combat time.
• 5: Louguan Sword. Stepping into this cell costs 1 second, and you have the option to pick up the sword by spending an additional 5 seconds (i.e. 6 seconds total). With the sword, you can chop through walls and monsters (turning them into open space) for only 1 second per move. The sword can be used unlimited times.
• M: Mashu. When you encounter this cell, you can "eat" it. It behaves like an open cell (costing 1 second) and does not affect any state.
• X: Teleport portal. When on a cell with X, you can either treat it as a normal cell (moving into it costs 1 second) or use the portal. Using the portal takes an additional 1 second and teleports you to any other X cell (the data may include many such cells). Note that when you pass through an X cell, you may choose not to teleport.

Movement Rules:

• You can move up, down, left, or right.
• Each move into a normally passable cell (or cell that you can pass because you have the required item) takes 1 second plus any additional time based on the cell type.
• For cells with monsters: if you do not have a sunflower or the sword, you must pay the combat cost (3 seconds for small monster or 8 seconds for large monster) when entering that cell.
• For walls (1): without the sword, you cannot pass. With the sword, you can chop the wall and move in 1 second.
• For the 5 (Louguan Sword) cell, if you do not already have the sword, you have two choices upon entering: either do not pick it up (costing 1 second) or spend an extra 5 seconds to acquire it (total 6 seconds). If you already have the sword, it acts as a normal cell costing 1 second.
• Once you pick up a sunflower or the sword, you keep it permanently.
• Be aware that monsters will respawn immediately after you leave their cell (i.e. if you re-enter, you will again have to pay the combat time unless you have a sunflower or the sword).
• It is possible that the optimal path includes bizarre moves such as backtracking.

Goal: Output the minimum time required to reach E from S. If there is no way to reach E, output:

We want to live in the TouHou World forever

May you have no regrets entering the Eastern world!

inputFormat

The first line contains two integers, N and M (the number of rows and columns, respectively). Each of the following N lines contains a string of M characters representing the grid.

outputFormat

Output a single line. If it is possible to reach E from S, output the minimum required time (in seconds). Otherwise, output "We want to live in the TouHou World forever".

sample

3 3
S21
404
E00

2