#0000A1

z-blinds

Long time ago, when Mister Little Z was really young, he used to play a game called "blind grandma" with his friends Steve, Robert and Milosh. The four of them have very specific rules of how they play the game. One of the players is a "Hunter" and the rest of the players run away from the Hunter. During the game all four of them are blindfolded and can't see where they are going


The playground for the game was an old storage facility, with a lot of boxes around. The storage room can be imagined as a tile of fields where some fields have a box on it and some don't. Also, the room is surrounded by walls. The players can walk on the fields that do not have a box on it. From a specific field they can move to any of the 8 fields surrounding it (as long as it is not a wall and there is not a box on that field)


Since all four of them are blindfolded they move in a specific way. All four of them are moving along a straight line, one field at the time. When the Hunter bumps into a wall or a box he rotates in clockwise direction until he can continue going, and he keeps going in that direction. Let's say that the Hunter was going North and has bumped into a box. If the North-East field is free, then the Hunter will go to that field and keep going in North-East direction. If the North-East field is not free than the Hunter will try to go East, etc, etc.. The rest of the guys that are running away from the Hunter move in a similar fashion, the only difference is that when they bump into a wall or a box they rotate counter-clockwise. All the players are moving with the same speed - one field per second (we assume that when they bump into a box or a wall, they immediately rotate to the new direction - they do not waste time rotating).


At the start of the game the four of them take random positions. The initial direction of the Hunter is North, and for the rest of the players the initial directions are East, West and South (each one has a different initial direction)


At a specific time, there can be more than one player on one field. When the Hunter and one of the guys who are running away from him find themselves on the same field, then the guy who was running away gets caught, and has to leave the storage room immediately. If the Hunter and some of the guys who are running away are on two adjacent fields and facing each-other, in the next step they will exchange the positions, and the Hunter will NOT catch the other player.


InputThe line of the standard input contains two integers N and M, that represent the dimensions of the storage room (2 <= N,M <= 25). Each of the next N lines contains M characters that represent the storage room with the initial positions of the players. "." - a dot represents an empty field, "#" - pound represents a field with a box on it. "N" represents the Hunter (and he is initially moving North). "E" represents the guy whose initial direction is East, "S" represents the guy whose initial direction is South and "W" represents the guy whose initial direction is West. The game starts at time T = 0.

OutputIn three lines of the standard output write three integers, the time when each of the three players that are running away get caught, or if the player never gets caught, ten write "NEVER". To the first line write the time when the "E"-player gets caught (or "NEVER"), to the second when "S" gets caught (or "NEVER"), and finally to the third line the time wen "W" gets caught (or "NEVER").

Input:
5 5
.....
.....
E...W
.....
..NS.

Output:
2
NEVER
2

Input:
5 8
#..#W...
.S..E..#
...#....
#....#..
N....#..

Output:
5
14
2

At time T = 2s W will be caught on the field (3,3). At time T = 5s E will be caught on the field (1,6). And finally at the time T = 14s, S will be caught at on the field (5,1).

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.