Description

Ever since the incident on the hill, Jack and Jill dislike each other and wish to remain as distant as possible. Jack and Jill must attend school each day; Jack attends a boys' school while Jill attends a girls' school. Both schools start at the same time. You have been retained by their lawyers to arrange routes and a schedule that Jack and Jill will adhere to so as to maximize the closest straight-line distance between them at any time during their trip to school.

Jack and Jill live in a town laid out as an n by n square grid (n ≤ 30). It takes 1 minute to walk from one location to an adjacent location. In maximizing the distance between Jack and Jill, you need only consider the distance between the locations they visit (i.e., you need not consider any intermediate points on the path they take from grid location to grid location). Some locations are impassable due to being occupied by rivers, buildings, etc. Jack must start at his house and walk continuously until he gets to school. Jill must start at her house at the same time as Jack and walk continuously until she arrives at her school. Jack's house and school are impassable to Jill, while Jill's house and school are impassable to Jack. Other grid locations that are impassable to both Jack and Jill are given in the input.

Input

The input consists of several test cases. Each test case begins with an integer n, followed by n lines with n characters representing a map of the town. In the map: • 'H' represents Jack's house • 'S' represents Jack's school • 'h' represents Jill's house • 's' represents Jill's school • '*' represents impassable locations • '.' represents passable locations

It is assumed that the map follows the standard cartographic convention where North is at the top and West is to the left. The last test case is followed by a line containing 0.

Output

For each test case, output three lines:

1. The first line should contain the closest distance between Jack and Jill during their trip, rounded to 2 decimal places.
2. The second line should contain Jack's route, represented as a sequence of directions ('N', 'S', 'E', or 'W') indicating his movement each minute from start until arrival at school.
3. The third line should contain Jill's route, formatted the same way as Jack's route.

If multiple valid route pairs exist, any one may be output. It is guaranteed that at least one solution exists. Separate the output for consecutive test cases with a blank line.

Sample Input 1

10
..........
...H......
.**...s...
.**.......
.**.......
.**.......
.**.......
.**.......
...S..h..*
..........
0

Sample Output 1

6.71
WWWSSSSSSSEEE
NEEENNNNNWWW

Source

Waterloo local 2004.01.31