Arrowland 举办了 2542 年欧洲青少年信息学奥林匹克竞赛。Arrowland 的形状是一个 $m$ 行（编号为 $0$ 到 $m-1$）$n$ 列（编号为 $0$ 到 $n-1$）的网格，每个单元格代表一个城市。设 $(r, c)$ 表示第 $r$ 行第 $c$ 列的单元格。参赛者被安置在单元格 $(0, 0)$，比赛大厅位于单元格 $(m-1, n-1)$。

Arrowland 的一个奇特旅游景点是某些城市拥有巨大的箭头。更奇怪的是，这些箭头每次只能顺时针旋转 90 度。每个箭头最初指向北、东、南或西。由于主办国的名称，EJOI 的组织者想要利用这些箭头。

参赛者将盲目地跟随箭头，无论他们当前的位置在哪里。从每个城市，他们只需移动到箭头所指的相邻城市。如果他们进入一个没有箭头的城市，或者如果他们离开了 Arrowland，他们就会停在那里，永远无法到达比赛大厅。由于 EJOI 组织者希望参赛者能从他们的住处（单元格 $(0, 0)$）到达大厅，他们可能需要旋转一些箭头。请帮助他们确定实现目标所需的最少旋转次数，或者告诉他们无论箭头如何指向，参赛者都无法到达大厅。

输入格式

第一行包含两个整数 $m$ 和 $n$，分别表示行数和列数。接下来的 $m$ 行每行包含 $n$ 个字符，表示箭头的初始方向（N - 北，E - 东，S - 南，W - 西，X - 该单元格没有箭头）。最后一行中的最后一个字符（即对应比赛大厅的字符）保证为 X。

在输入矩阵中，北、东、南和西的方向与标准地图上的含义相同。因此，字符 N 表示“向上”，E 表示“向右”，S 表示“向下”，W 表示“向左”。

输出格式

输出 EJOI 组织者必须执行的最少旋转次数。如果任务是不可能的，则输出 $-1$。

数据范围

• $1 \le m, n \le 500$。
• 每个单元格包含以下字符之一：N, E, S, W, X。

子任务

• 10 分：$m = 1$；每个单元格包含字符 E 或字符 X。
• 12 分：$m = 1$。
• 12 分：$m = n = 3$。
• 16 分：$m = 2$。
• 50 分：无附加限制。

样例

输入 1

3 3
EES
SSW
ESX

输出 1

3

说明 1

在这种情况下，一种可能的最佳方案是将单元格 $(1, 2)$ 中的 W 通过旋转三次变为 S。

输入 2

3 3
EES
SSW
EEX

输出 2

0

说明 2

在这里，EJOI 组织者不需要做任何改变，参赛者就能到达比赛大厅。

输入 3

3 4
EXES
WSNS
XNNX

输出 3

4

说明 3

将单元格 $(0, 0)$ 中的箭头旋转一次（得到 S），将单元格 $(1, 0)$ 中的箭头旋转两次（得到 E），并将单元格 $(2, 1)$ 中的箭头旋转一次（得到 E）。