Journey in the Dark

Petro Pyatochkin spent the evening exploring a fascinating labyrinth and didn't realize when night fell. Now in the dark, he can only see the labyrinth's layout on his mobile phone and the starry sky, where he quickly identified the North Star. The labyrinth is represented as a rectangular grid of symbols: dots "." indicate open spaces with a side length of one step, while hashes "#" represent walls. The top edge of the grid points north, and the right edge points east.

Petro's goal is to find the exit, marked with a cross on the plan. This single exit is a distinct area, and Petro will fall through it as soon as he steps on it. Unfortunately, Petro is unaware of his exact starting position within the labyrinth.

A route consists of a series of commands such as "step north", "step south", "step east", and "step west". If a step would lead Petro into a wall or out of the labyrinth, that step is ignored, and the route continues.

Your task is to determine a route that Petro can follow to reach the exit in a finite number of steps, regardless of his starting position, or to establish that such a route is impossible.

Input

The first line of the input contains two natural numbers H and W (1 ≤ H, W ≤ 10).

The next H lines each contain W characters: ".", "#", or "+", representing open spaces, walls, and the exit, respectively. This provides the labyrinth's layout, where the first line corresponds to the northern edge, and the last character of each line corresponds to the eastern edge.

Output

The output should be a single line containing a sequence of the symbols "N", "S", "E", and "W", indicating movements north, south, east, and west, respectively. This sequence should describe a route that Petro can take to reach the exit in a finite number of steps, regardless of his starting position. There may be multiple valid routes; any one of them should be output, with the total number of steps not exceeding 10000.

If no such route exists, the output should be the two symbols "NO".

Explanation: Consider example 3. It can be verified that, regardless of the starting cell, Petro will eventually reach the exit.

For example, starting from the cell (2, 1) in the second row and first column.

Once the exit is reached, further steps in the route are irrelevant.