A. Always Right
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is an expert at solving maze puzzles. One day, her friend Bob gave her a challenge.

Bob: Normal maze puzzles are too easy for you, can you solve a maze without turning left?

Alice: It's simple! Just turn right three times in the same cell!

Bob: What if you must move one step forward before turning right?

Alice doesn't know the solution and asks for your help.

You are given the maze as a $$$N \times M$$$ grid. Different cells are represented as follows:

  • # represents a wall cell.
  • . represents an empty cell.
  • S represents the starting cell.
  • E represents the ending cell.

When the cell in front of you is not a wall cell, you can perform one of the following moves:

  1. Move forward one cell.
  2. Move forward one cell and turn to your right.

Can you find the minimum number of moves required to reach the ending cell from the starting cell, or determine that it is not possible to do so?

Input

The first line contains two positive integers, $$$N, M$$$, $$$(4 \leq N, M \leq 800)$$$.

The following $$$N$$$ lines each contain $$$M$$$ characters, representing the maze.

The final line contains a single character, U (up), D (down), L (left) or R (right), denoting your initial direction.

It is guaranteed that all cells in the outermost layer are wall cells and there are exactly one starting cell and ending cell.

Output

Output a single integer, the minimum number of moves to reach the ending cell, or $$$-1$$$ if the ending cell cannot be reached.

Examples
Input
6 7
#######
#.....#
#..##.#
#.S...#
#E....#
#######
U
Output
12
Input
5 4
####
#E.#
#S.#
#..#
####
R
Output
5