Image generated by Google Gemini.

After a long night of karaoke, izakaya hopping, and suspiciously strong umeshu to impress the boss, our beloved salaryman is on a mission: to get home before sunrise.

Unfortunately, he's still quite drunk. Due to his wobbly state, he can only take up to three consecutive steps in the same direction. If he tries a fourth, he trips, falls, and passes out on the spot.

You're given a grid representing the city. Each cell is either an open tile (.) or a wall (#). The salaryman starts at position S and must reach his apartment at position E. From any open tile, he can move one cell up, down, left, or right but never more than three times in a row in the same direction.

Your task is to determine the minimum number of steps required for the salaryman to reach his home safely without breaking the movement rule. If no valid path exists, return -1.

Input

The first line contains two integers H and W (1 ≤ H, W ≤ 100): the height and width of the maze.

Each of the next H lines contains a string of length W, consisting of the characters '.', '#', 'S', or 'E':

• . : open tile
• # : wall
• S : starting position (appears exactly once)
• E : target position (appears exactly once)

Output

Print a single integer, the minimum number of steps required to reach E from S, without violating the movement restriction.

Example

Sample Input:

3 8
########
S......E
########

Output:

11

Explanation:

A sober salaryman might do this in 7 steps, but you're zigzagging your way across town like a malfunctioning Roomba. The shortest valid path takes 11 steps under the "three-step" wobble rule. After going right three steps, you go back one step, then right three more, and finally down to reach home. Remember, no more than three steps in the same direction or you'll end up face-first in a puddle of last night's regrets!

Sample Input:

5 5
#####
S#E.#
.##.#
....#
#####

Sample Output:

8