Rotating Penguin Maze

A baby penguin has to reach the fish someone hid inside a maze, and it has to get there as fast as possible. The penguin reads a compass, so it understands the four instructions E, N, W and S. Each instruction moves it exactly one tile in that direction.

The maze has one more device. Some tiles carry a pressure plate, and when the penguin steps on such a tile the whole iceberg holding the maze turns 90 degrees counter clockwise. The penguin turns with the iceberg, so it never notices. The compass needle does not turn with the iceberg, so every time a plate fires you have to change the instructions you still have to give.

The maze always has exactly one path from the starting tile to the goal tile. Between every pair of tiles there is exactly one path, and the starting tile never carries a pressure plate.

The first line contains the number of test cases $T$.

The first line of each test case contains the maze size $X$ in the x direction and $Y$ in the y direction. The next line contains four integers $p_x$, $p_y$, $g_x$, $g_y$, the penguin's starting coordinates and the coordinates of the goal tile. Then follow $Y$ lines of $X$ characters each.

One character describes one tile. Its value is written as a single base 32 digit ($0$, $1$, ..., $9$, $A$, $B$, ..., $V$) and is the sum of the features the tile contains. An east going passage adds $1$, a north going passage adds $2$, a west going one adds $4$, and a south going one adds $8$. A pressure plate adds $16$, written as $G$. A tile value of $H$, that is $17$, means the tile has an east going passage and a pressure plate.

The $x$ coordinate grows from left to right and the $y$ coordinate grows from top to bottom. Tile $(x, y)$ is character number $x+1$ of line number $y+1$, and north is the direction in which $y$ decreases.

• $0 < T \le 100$
• $0 < X \le 500$
• $0 < Y \le 500$
• $0 \le p_x, g_x < X$
• $0 \le p_y, g_y < Y$

For each test case print one line with the compass instructions that guide the penguin along the shortest path to the tile holding the fish, written in order with no separator. Each instruction moves the penguin exactly one tile in the given direction. If the penguin already stands on the goal tile, print an empty line.