Basic Wall Maze

In this problem you must solve a very simple maze made of:

1. a 6 by 6 grid of unit squares
2. 3 walls, each of integer length between 1 and 6, placed either horizontally or vertically along the grid lines to separate squares
3. one start marker and one end marker, each occupying a single square

An example maze looks like this:

You must find a shortest path from the square holding the start marker to the square holding the end marker. Only moves between adjacent squares are allowed; two squares are adjacent when they share an edge and that edge is not blocked by a wall. You may never leave the grid.

The input consists of several test cases.

Each test case consists of five lines:

• The first line contains the column and the row of the square holding the start marker.
• The second line contains the column and the row of the square holding the end marker.
• The third, fourth and fifth lines each describe one wall.

Squares are addressed by a column in $1 \dots 6$ (counted from the left) and a row in $1 \dots 6$ (counted from the top).

A wall is given by its two end points. For a horizontal wall the left end point comes first, then the right end point; for a vertical wall the upper end point comes first, then the lower end point. Each end point is two integers: its distance from the left side of the grid, followed by its distance from the top side of the grid (both in $0 \dots 6$).

You may assume that the three walls do not cross one another, although they may touch at a grid corner, and that all wall end points lie on the grid. A valid path from the start marker to the end marker is always guaranteed to exist.

The last test case is followed by a line containing two zeros, which must not be processed.

For each test case, output on its own line a shortest path from the start marker to the end marker.

The path is written as a string of moves, where each move is one of:

• N — one square up
• E — one square right
• S — one square down
• W — one square left

Several different shortest paths may exist. To make the answer unique, print the lexicographically smallest shortest-path string, comparing the strings as ordinary text so that the move letters rank E < N < S < W.

If the start and end markers lie on the same square the path is empty, so print an empty line.