你发现自己身处一座偏远的岛屿上，正在寻找传说中失落的宝藏。然而，尽管你手中掌握着直通宝藏的路线指引，但你遇到了一个问题。原来你的探险队中混入了一个破坏者，他在某个时刻篡改了这些珍贵的指引，导致它们不再指向宝藏。

这座岛屿可以看作是一个矩形网格，指引是从给定的起始位置开始，在网格中进行的一系列东/西/北/南方向的移动。这些指引原本直通宝藏（可能涉及绕过障碍物），意味着到达宝藏的路径是最短的。然而，破坏者随意地将指引中的每一步替换为其他三个方向中的任意一个。换句话说，任何“西”方向的步骤都被替换成了“东”、“北”或“南”。这种替换是针对每一步独立进行的，所以一个“西”可能被替换成了“北”，而另一个“西”可能被替换成了“南”，以此类推。

由于这种破坏，这些指引看起来几乎毫无用处。但也许它们仍然可以用来缩小搜索范围。请编写一个程序，找出所有可能的宝藏位置。

输入格式

输入的第一行包含两个整数 $w$ 和 $h$ ($3 \le w, h \le 1000$)，分别表示地图的宽度和高度。接下来是 $h$ 行，每行包含 $w$ 个字符，描述地图。每个字符要么是表示可行走空间的 ‘.’，要么是表示障碍物（如水域、茂密森林或山脉）的 ‘#’，或者是表示指引起始点的 ‘S’。

最后一行包含一个字符串 $I$ ($1 \le |I| \le 10^5$)，仅由字符 ‘N’、‘W’、‘S’、‘E’ 组成，表示被篡改后的指引序列。

地图中恰好有一个 ‘S’，且其边界仅由障碍物单元格组成。被篡改的指引序列保证至少存在一个可能的宝藏位置。

输出格式

输出与输入格式相同的地图（不包含第一行指定的维度信息），并将所有可能的宝藏位置用感叹号（‘!’）标记。

样例

样例输入 1

5 5
#####
#...#
#.S.#
#...#
#####
N

样例输出 1

#####
#...#
#!S!#
#.!.#
#####

样例输入 2

7 5
#######
#..#..#
#..S..#
#..#..#
#######
ESS

样例输出 2

#######
#!.#..#
#..S..#
#..#..#
#######