A rectangular polygon is a polygon with each of its sides
parallel to either the X or Y axis. Therefore, each of its vertex
angles is exactly either 90 or 270 degrees.
Your team's task is to write a program that will order vertices of
such a polygon.
The input will describe several polygons. The description of each
polygon starts on a line containing the number of vertices as a single
positive integer N, (N <= 1000). The following N lines are the
vertices of the polygon. Each line contains a pair of integer
numbers (Xi, Yi) giving the coordinates of a vertex,
|Xi| <= 10000, |Yi| <= 10000.
The coordinate values are
separated from each other by whitespace.
The X axis aims East, the Y axis North.
All vertices are given and each of them is
listed exactly once. The vertices may appear in the input in any order.
The polygon does always exist, it is closed,
its sides do not intersect and it contains no "holes" inside
(its border is formed by one closed line).
Input ends with a vertex count of zero.
Using the letters "N", "E", "W", "S" (North, East, West, South),
describe each polygon as a directional walk that starts from the first vertex
given and proceeds clockwise. Print the letters for each polygon in order
on a single line starting in the first column. Do not print any embedded or
trailing whitespace characters on the line.
Sample Input
4
0 0
2 2
0 2
2 0
6
1 1
2 2
0 1
1 0
0 2
2 0
0
Output for the Sample Input
NESW
WNESWN
File translated from
TEX
by
TTH,
version 3.77. On 18 Nov 2007, 08:43.