Problem Description

This problem is translated from CCO 2015 Day2 T1 "Cars on Ice"

Guarding the bank on Christmas Eve is incredibly dull. This is why Barry wants to go ice skating near the parking lot. However, since other guards have parked their cars there, the parking lot is not empty. Barry decides to push their cars out of the parking lot. He notices that the parked cars are facing one of the four directions: north, south, east, or west. Because the parking lot is icy, pushing a car will cause it to slide until it exits the parking lot or crashes into another car. These cars can only be pushed in the direction they are facing. To avoid crashes, Barry asks for your help to calculate the order in which he should push the cars out of the parking lot, so he can clear the parking lot.

Input Format

The first line contains two integers $N, M$, representing the number of rows and columns of the parking lot.
The next $N$ lines, each containing $M$ characters, describe the parking lot. Where . represents an empty spot, and N, E, W, S represent a car facing north, south, east, and west, respectively.

Output Format

Output the order in which the cars should be pushed out without causing crashes. Each car should be output in the format $(r, c)$, where $(r, c)$ is the coordinate of the car in the parking lot, with $(0, 0)$ being the top-left corner and $(N-1, M-1)$ being the bottom-right corner.
It is guaranteed that there is at least one valid solution. If there are multiple solutions, output any one.

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

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

Sample Output #2

(1,1)
(2,1)

Notes

Sample Explanation 1

The only car that is not blocked by other cars at the start is at $(4,3)$. When this car is pushed out to the right side of the parking lot, the car above it (at $(1,3)$) can be pushed out, followed by the car at $(1,1)$, and finally the car at $(4,1)$. The parking lot is then cleared.

Sample Explanation 2

Both cars can be the first to be pushed out of the parking lot, so Sample Output 2 is correct, and the output with the reverse order is also correct.

Data Range

For $70\%$ of the test cases, $1 \leq N, M \leq 100$.
For $100\%$ of the test cases, $1 \leq N, M \leq 2000$.

见题面 Input 部分

见题面 Output 部分