Description

Occasionally, WWY finds a treasure map with size of $n*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.

avatar

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

Format

Input

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

lines follwed, each line has m characters each characters$\in \left \{ '\$','\#' \right \}$.

Output

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.

Samples

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

5
ESESE

Hints

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

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