Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1176
Die and Chessboard

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Imagine you have a six-sided die standing on infinite chessboard that have that have field side length exactly equal to die edge length. You can move die onto the north, south, west or east directions by turning the die around the corresponding edge. Your goal is to find any sequence of such moves that would bring the die from initial position (includes initial orientation of the die) into it's target position that would be specified in the input data so that target digit (also specified by input data) becomes written on a die's upper side.

Initial die orientation is as follows: top side - 1, bottom side - 2, north side - 3, south side - 4, west side - 5, east side - 6. Initial die position is (0, 0). First digit in a position represents west-to-east direction (greater number - to east) and the second one - south-to-north position (greater number - to north).

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.


The input consists of single line that contains three integers: -1000 <= X <= 1000 - desired west-to-east position of the die, -1000 <= Y <= 1000 - desired south-to-north position of the die and 1 <= M <= 6 - number that should be at top when die is finished moving.


Output should contain a route that solves the problem coded as follows: S - going south, N - going north, E - going east, W - going west. As the last step of the route is executed the die should stand in a desired location with a desired digit on upper side. Route steps should be printed without any spaces between grouped in some lines so all the lines (probably excluding last one) contain exactly 80 characters (route steps).

Sample Input


1 1 5

Sample Output


Submit    Status