---

题目描述

国际行星制图中心（ICPC）使用漫游车来探索其他行星的表面。众所周知，其他行星都是平坦的表面，可以被完美且均匀地离散化为一个矩形网格结构。这个网格中的每个单元格要么是平坦的，可供漫游车探索；要么是岩石的，无法通行。

今天，他们全新的「大黄蜂」漫游车正式发射。该漫游车将使用一种简单的算法来探索行星。在内部，漫游车维护着一个方向顺序，即北、东、南、西四个方向的一个排列。当漫游车进行移动时，它会遍历其方向顺序，选择第一个不会使其移出该行星表面或进入无法通行的岩石区域的方向，并朝该方向移动一步。

在两次连续的移动之间，漫游车可能会被宇宙射线击中，导致其方向顺序被替换为另一个不同的顺序。ICPC的科学家们有一份漫游车的移动日志，但很难通过手动方式判断其方向顺序是否以及何时发生了改变。根据漫游车已经进行的移动，它可能被宇宙射线击中的最少次数是多少？

---

输入格式

输入的第一行包含两个整数 $r$ 和 $c$，其中 $r$ $(1 \leq r \leq 200)$ 是行星上的行数，$c$ $(1 \leq c \leq 200)$ 是列数。行从北向南延伸，列从西向东延伸。

接下来的 $r$ 行，每行包含 $c$ 个字符，代表行星的地形布局。每个字符要么是 #，代表岩石区域；要么是 .，代表平坦区域；要么是 S，代表平坦区域，同时也是漫游车的起始位置。网格中恰好有一个 S。

再下一行包含一个字符串 $s$，其中每个字符是 N、E、S 或 W 之一，代表漫游车执行的移动序列。字符串 $s$ 的长度在 $1$ 到 $10000$ 个字符之间（含）。所有的移动都会到达平坦区域。

---

输出格式

输出为了与漫游车所做的移动保持一致，其方向顺序可能改变的最少次数。

---

样例 1

输入

5 3
#..
...
...
...
.S.
NNEN

输出

1

解释
漫游车的方向顺序可能如下。在第一步移动中，它要么优先向北，要么优先向南再向北。注意在后一种情况下，它不能向南移动，因为会掉出该行星的表面。在第二步移动中，它必须优先向北。在第三步移动中，它必须优先向东。在第四步移动中，它可以优先向北，或者优先向东再向北。因此，它有可能在第二步和第三步移动之间恰好被宇宙射线击中一次，使其方向顺序从 N??? 变为 EN??，其中 ? 代表任何剩余的方向。

---

样例 2

输入

3 5
.###.
....#
.S...
NEESNS

输出

0

解释
漫游车可能以方向顺序 NESW 开始，这个顺序与它所做的所有移动都一致。

---

样例 3

输入

3 3
...
...
S#.
NEESNNWWSENESS

输出

4

---