로봇 레이스

직사각형 보드에 Y 로봇과 F 로봇, 그리고 목표 칸 X가 있다. 보드의 각 칸은 빈 칸, 장애물, 두 로봇의 시작 칸, 목표 칸 중 하나이다. Y 로봇이 F 로봇보다 먼저 목표 칸에 도착하면 승리한다. 두 로봇이 동시에 도착하거나 Y 로봇이 목표 칸에 도착하지 못하면 승리하지 못한다.

명령은 다음 네 종류이다.

• S: 남쪽으로 한 칸 이동
• N: 북쪽으로 한 칸 이동
• E: 동쪽으로 한 칸 이동
• W: 서쪽으로 한 칸 이동

시간이 지날 때 두 로봇은 같은 명령을 듣는다. 각 로봇은 그 명령을 수행하거나 무시할 수 있다. 명령을 수행하면 보드를 벗어나거나 장애물이 있는 칸으로 이동하게 되는 경우, 그 로봇은 자동으로 그 명령을 무시한다. 두 로봇은 각각 자신이 목표 칸에 가능한 한 빨리 도착하도록 최적으로 선택한다.

시작 시간 T는 명령 문자열의 0번 위치부터 세었을 때 T번째 문자부터 명령을 듣기 시작한다는 뜻이다. Y 로봇의 승리가 보장되는 가장 작은 시작 시간 T를 구하라. 그런 시작 시간이 없다면 -1을 출력한다.

첫째 줄에 보드의 세로 길이 N과 가로 길이 M이 주어진다. N과 M은 50 이하의 자연수이다.

다음 N개의 줄에는 보드가 주어진다. .은 빈 칸, #은 장애물, Y는 Y 로봇의 시작 위치, F는 F 로봇의 시작 위치, X는 목표 위치를 뜻한다. Y, F, X는 각각 정확히 하나씩 주어진다.

마지막 줄에는 명령 문자열이 주어진다. 명령 문자열의 길이는 최대 2500이며, S, E, N, W로만 이루어져 있다.

첫째 줄에 Y 로봇의 승리가 보장되는 가장 작은 시작 시간을 출력한다. 그런 시작 시간이 없으면 -1을 출력한다.