题目描述

你和朋友在一块矩形棋盘上操纵两个机器人比赛。棋盘中的每个格子可能为空地、障碍、某个机器人的起点或终点。只有当你的机器人严格早于朋友的机器人到达终点时，你才获胜；如果两者同时到达，或者两者最终都无法到达终点，你都失败。

每个时间单位会同时向两个机器人发送同一个移动命令：

• S：向南移动一格，即行号加 $1$；
• N：向北移动一格，即行号减 $1$；
• E：向东移动一格，即列号加 $1$；
• W：向西移动一格，即列号减 $1$。

收到命令后，每个机器人都可以选择执行该命令或忽略它。如果执行命令会离开棋盘或进入障碍格，则该命令自动被忽略。两个机器人允许同时位于同一个格子。每个机器人都会作出最优决定，使自己尽早到达终点。

棋盘字符含义如下：

• .：空地；
• #：障碍；
• Y：你的机器人的起点；
• F：朋友的机器人的起点；
• X：终点。

原始命令由若干字符串片段依次拼接而成。拼接后字符串的第 $i$ 个字符表示时间 $i$ 的命令，下标从 $0$ 开始。

你可以选择一个开始时间 $T$。比赛从时间 $T$ 开始时，仅使用拼接命令串中下标从 $T$ 开始的命令，所有下标小于 $T$ 的命令都被两个机器人忽略。

求能够保证你的机器人获胜的最早开始时间。如果不存在这样的开始时间，输出 $-1$。

输入格式

第一行输入两个整数 $H,W$，表示棋盘的行数和列数。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串，描述棋盘。

接下来一行输入整数 $K$，表示命令字符串片段的数量。

接下来 $K$ 行，每行一个只包含 S、N、E、W 的字符串。将这 $K$ 个字符串按输入顺序拼接，即得到完整命令串。

输出格式

输出一个整数，表示最早能够保证你获胜的开始时间；若不存在，输出 $-1$。

样例输入

2 2
#F
YX
1
NES

样例输出

0

数据范围

• $1\le H,W\le50$；
• 棋盘只包含 . # Y F X 五种字符；
• Y、F、X 各恰好出现一次；
• $1\le K\le50$；
• 每个命令片段长度在 $1$ 到 $50$ 之间；
• 所有命令字符均为 S、N、E、W 之一。