{"problem":{"name":"F. Coupled Polygons","description":{"content":"A nice polygon is defined as: 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 c","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":9000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10054F"},"statements":[{"statement_type":"Markdown","content":"A nice polygon is defined as:\n\nA 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.\n\nA nice polygon B is said to be a perfect match for a nice polygon A if:\n\nFor example, the light-colored polygon NNNEEESSWNWSSW is a perfect match for the dark-colored polygon EEEESSSSWWWNNESENNWWWN, illustrated as follows:\n\nIn 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. \n\nThe following two polygons are not a perfect match for each other either, as they cannot form a square without overlapping each other\n\nIn 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.\n\nGiven a nice polygon A, your task is to find a nice polygon B such that B is a perfect match for A.\n\nThe 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.\n\nEach 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.\n\nFor 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.\n\n## Input\n\nThe 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.\n\n## Output\n\nFor 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ A $ be a string over the alphabet $ \\Sigma = \\{N, E, W, S\\} $, representing a closed polygonal path in the plane, where each character denotes a unit-length step in the corresponding cardinal direction.  \n\nLet $ P_A $ be the polygonal path defined by $ A $, starting at the origin and following the sequence of directions. The path is closed if and only if the net displacement is $ (0,0) $.  \n\nA polygon $ B $ is a **perfect match** for $ A $ if:  \n1. $ P_A $ and $ P_B $ together form a **filled square** with **no holes** and **no overlaps**.  \n2. $ P_B $ is the **smallest** such polygon (in terms of enclosed area) that, when combined with $ P_A $, forms a square.  \n3. The union $ P_A \\cup P_B $ bounds a **solid axis-aligned square**.  \n\n**Constraints**  \n1. $ |A| \\leq 100{,}000 $  \n2. $ A $ represents a **closed** polygon (net displacement: $ \\sum \\vec{d}_i = (0,0) $)  \n3. The square formed by $ A $ and $ B $ must have integer side length and axis-aligned boundaries.  \n\n**Objective**  \nGiven $ A $, find the lexicographically smallest string $ B \\in \\Sigma^* $ such that $ B $ is a perfect match for $ A $.  \nIf no such $ B $ exists, output `NONE`.  \n\n**Lexicographic order**: $ N < E < S < W $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10054F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}