在圣诞节之夜守卫银行可能会非常无聊。这就是 Barry 决定在停车场滑一会儿冰的原因。然而，停车场里并不空，因为其他保安的车停在那里。所以 Barry 决定把他们的车推离停车场。他注意到这些车分别朝向北、南、东或西。由于停车场结冰了，推动一辆车会使它滑动，直到它离开停车场或撞到另一辆车。车只能沿着它们朝向的方向推动。为了不让车发生碰撞，Barry 需要你的帮助，找出他必须以什么顺序推动这些车，才能清空停车场。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 2000$)，表示停车场的行数和列数。接下来的 $N$ 行，每行包含 $M$ 个字符，表示停车场本身，其中 '.' 表示空位，而 'N'、'S'、'E' 和 'W' 分别表示一辆车（分别朝向北、南、东或西）。

对于该问题至少 70% 的分数，满足 $N \le 100$ 且 $M \le 100$。

输出格式

输出必须推动车辆以清空停车场且不发生碰撞的顺序。 以 $(r, c)$ 的形式输出每辆车，其中 $r$ 和 $c$ 是该车在停车场上的坐标（$(0, 0)$ 是左上角，$(N - 1, M - 1)$ 是右下角）。

你可以假设总会至少存在一个有效的解。 如果存在多个可能的解，输出任意一个有效解即可。

样例

样例输入 1

5 5
.....
.E.S.
.....
.....
.N.E.

样例输出 1

(4,3)
(1,3)
(1,1)
(4,1)

说明 1

最初没有被其他车挡住的唯一一辆车是位于 $(4, 3)$ 的那辆。在它被推向停车场右侧后，它上面的车（位于 $(1, 3)$）就可以被推动，接着是位于 $(1, 1)$ 的车，最后是位于 $(4, 1)$ 的车，从而清空停车场。

样例输入 2

4 3
...
.N.
.S.
...

样例输出 2

(1,1)
(2,1)

说明 2

两辆车中的任意一辆都可以先被推动以清空停车场，因此该输出是可以接受的（以相反顺序输出行也是可以的）。