Cars on Ice

Barry, a bored bank guard on Christmas night, has decided to clear the parking lot near his station so he can go skating. The parking lot is a rectangular grid with R rows and C columns. Some cells are occupied by cars, each facing one of the four cardinal directions (North, East, South, or West). When a car is pushed, it slides in the direction it faces until it leaves the grid. However, a car can be pushed only if all cells in its sliding path (i.e. every cell from the one immediately adjacent in its direction of travel until the grid boundary) are empty at that time. Once pushed, the car leaves the parking lot (its cell becomes empty), and then the next car may be pushed. Your task is to determine an order in which Barry can push all the cars out of the lot without any car colliding with another still parked.

Note: It is guaranteed that an order exists. If several orders are possible, output any one of them. Rows and columns are 1-indexed.

inputFormat

The first line contains two integers R and C (1 ≤ R, C ≤ 1000), which describe the dimensions of the parking lot.

The next R lines each contain a string of C characters. Each character is either a dot ('.') representing an empty cell or one of the characters 'N', 'E', 'S', 'W', indicating a parked car facing North, East, South, or West respectively.

outputFormat

Output several lines. Each line should contain two space‐separated integers representing the row and column of a car that is pushed. The order of the output lines represents the sequence in which the cars are removed from the parking lot. It is guaranteed that following this order, every car is pushed when its sliding path (from the cell adjacent in its facing direction until leaving the grid) is free (i.e. contains no car).

sample

3 3
.N.
W.E
...

1 2
2 1
3 3