Robot Race

A rectangular board contains robot Y, robot F, and a target cell X. Each cell is empty, blocked, one robot's starting cell, or the target cell. Robot Y wins if it reaches the target cell before robot F. If the two robots arrive at the same time, or if robot Y cannot reach the target cell, robot Y does not win.

There are four kinds of commands.

• S: move one cell south
• N: move one cell north
• E: move one cell east
• W: move one cell west

As time passes, both robots hear the same command. Each robot may either follow that command or ignore it. If following the command would move a robot outside the board or into a blocked cell, that robot automatically ignores the command. Each robot chooses optimally to reach the target cell as early as possible.

A start time T means the robots start listening from the character at 0-based position T in the command string. Find the smallest start time T for which robot Y is guaranteed to win. If no such start time exists, output -1.

The first line contains the board dimensions N and M. Both N and M are positive integers not greater than 50.

The next N lines describe the board. . is an empty cell, # is a blocked cell, Y is the starting position of robot Y, F is the starting position of robot F, and X is the target position. Each of Y, F, and X appears exactly once.

The last line contains the command string. Its length is at most 2500, and it consists only of S, E, N, and W.

Print the smallest start time for which robot Y is guaranteed to win. If no such start time exists, print -1.