401847: GYM100541 F Coupled Polygons

A nice polygon is defined as:

• A non-self-intersecting polygon;
• All edges are parallel to the horizontal or vertical axes;
• All edges have integer unit of measure length.

A nice polygon can be encoded by a string consisting of only four type of characters: N, E, W and S standing for North, East, West and South, respectively. The polygon can be reconstructed from the string by drawing the edge following the direction described, with each character represents exactly 1 unit long. For example, the following 2 polygons are encoded as EEEESSSSWWWNNESENNWWWN and NNNEEESSWNWSSW, respectively.

A nice polygon B is said to be a perfect match for a nice polygon A if:

• Only by moving the polygons horizontally or vertically, these two polygons can be positioned so that they do not overlap each other and form a square with no holes inside (i.e., the area of the formed square is equal to the sum of the two polygons’ areas)
• The area of B is minimum.

For example, the light-colored polygon NNNEEESSWNWSSW is a perfect match for the dark-colored polygon EEEESSSSWWWNNESENNWWWN, illustrated as follows:

In contrary, the following two polygons (light and dark) cannot form a square with no holes inside, hence they cannot be a perfect match for each other.

The following two polygons are not a perfect match for each other either, as they cannot form a square without overlapping each other

In the following example, the two polygons form a perfect square but the light-colored polygon is not a perfect match for the dark-colored polygon, as the light-colored polygon is not the smallest one to form a square. The dark-colored polygon is, however, a perfect match for the light-colored polygon.

Given a nice polygon A, your task is to find a nice polygon B such that B is a perfect match for A.

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 30. The following lines describe the datasets.

Each dataset has one string representing the polygon A on a single line. The string consists of only N, E, W and S and contains at most 100, 000 characters.

For each dataset, write on one line a string representing the nice polygon B that is a perfect match for A. If there are multiple answers, write out the one that come first lexicographically. If there is no solution, write out the string NONE on one line.

1
WSSEEENNNNWWWWSEEESSWN

EEESSWNWSSWNNN