Occasionally, WWY finds a treasure map with size of $n \times m$.

This map consists of only two characters: '$' and ‘#’.

'$'$\;$: An empty cells$\;$(WWY can walk on it).

'#'$\;$: A cell full of rock$\;$(WWY cannot walk on it).

WWY now is in $(1,1)$ coordinates (top left corner) and the treasure house is in $(n,m)$ coordinates (lower right corner).

Every second, WWY can chose one direction from $\{North, South, West, East\}$ and fly one step towards it.

Can you help WWY find the path to the treasure house with the minimum seconds?

The first line of input is an integer $n\;(1 \leq n \leq 10)$ and an integer $m\;(1 \leq m \leq 10)$.

$n$ lines follwed, each line has $m$ characters $\; each \; character \in \{'\$', '\#'\}$.

The output has two lines.

The first line prints the minimum seconds to arrive the treasure house.

The second line prints several characters for $N,S,W,E$ representing $North,South,West,East$. If there are many paths with the same minimum seconds, please print the path with maximum dictionary.

It is guarantees that there must have a path for arriving the treasure house.

3 4
$$#$
#$$$
##$$

5
ESESE

Arriving from $(1,1)$ to $(3,4)$, the minimum seconds is $5$.

The paths with the minimum seconds are $ESEES$ and $ESESE$, and $ESESE$ is the maximum dictionary path with the minimum seconds.