题目描述

本题译自 CCO 2015 Day2 T1「Cars on Ice」

在圣诞夜守卫银行是一件非常无聊的事情。这就是 Barry 想要去停车场附近溜冰的原因。然而因为其他守卫把车停在了那里，停车场并不是空的。所以 Barry 决定把他们的车推出停车场。他注意到那些停着的车面对的方向是东南西北之一。因为停车场结冰了，所以推一辆车将会使得他滑行直至离开停车场或撞上其他的车。这些车只能朝他们面向的方向推。为了不撞车，Barry 找你帮忙，让你帮他计算出将车推出停车场的顺序，以便他清空停车场。

输入格式

第一行包括两个整数 $N,M$，表示停车场的行列数。
接下来 $N$ 行每行 $M$ 个字符，描述一个停车场。其中 . 代表这是一个空的车位，而 N, E, W, S 表示一辆车，分别表示这辆车面朝北、南、东、西。

输出格式

输出在不发生撞车的情况下将车推出的顺序，每辆车按格式 $(r,c)$ 输出，其中 $(r,c)$ 是车在停车场中的坐标，$(0,0)$ 为左上角，$(N-1,M-1)$ 为右下角。
保证至少有一个有效解，如果有多个解，输出任意一个。

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

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

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

(1,1)
(2,1)

数据范围与提示

对于 $70\%$ 的数据，$1\le N,M \le 100$；

对于 $100\%$ 的数据，$1\le N,M \le 2000$。