Ingenuity-2
Contest: Codeforces Round 946 (Div. 3)
Difficulty rating: 1400
Tags: constructive algorithms, greedy, implementation

Let's imagine the surface of Mars as an infinite coordinate plane. Initially, the rover Perseverance-2 and the helicopter Ingenuity-2 are located at the point with coordinates $$$(0, 0)$$$. A set of instructions $$$s$$$ consisting of $$$n$$$ instructions of the following types was specially developed for them:

- N: move one meter north (from point $$$(x, y)$$$ to $$$(x, y + 1)$$$);
- S: move one meter south (from point $$$(x, y)$$$ to $$$(x, y - 1)$$$);
- E: move one meter east (from point $$$(x, y)$$$ to $$$(x + 1, y)$$$);
- W: move one meter west (from point $$$(x, y)$$$ to $$$(x - 1, y)$$$).

Each instruction must be executed either by the rover or by the helicopter. Moreover, each device must execute at least one instruction. Your task is to distribute the instructions in such a way that after executing all $$$n$$$ instructions, the helicopter and the rover end up at the same point, or determine that this is impossible.

Input format:
The first line of input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of instructions.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of the characters 'N', 'S', 'E', 'W' — the sequence of instructions.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$.

Output format:
For each test case, if the required distribution of instructions exists, output a string $$$p$$$ of length $$$n$$$ consisting of the characters 'R', 'H'. If the $$$i$$$-th operation should be executed by the rover, then $$$p_i=\text{R}$$$, if the $$$i$$$-th operation should be executed by the helicopter, then $$$p_i=\text{H}$$$. If there are multiple solutions, output any of them.

Otherwise, output NO.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's consider the first example: the string $$$S = \texttt{NENSNE}$$$. One of the possible solutions, shown in the figure below, is $$$p = \texttt{RRHRRH}$$$, using which both the rover and the helicopter will end up one meter north and one meter east.

For WWW, the solution is impossible.

Example input:
10
6
NENSNE
3
WWW
6
NESSWS
2
SN
2
WE
4
SSNN
4
WESN
2
SS
4
EWNN
4
WEWE

Example output:
RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH

Editorial:
For the string $$$S$$$, calculate the 2D-coordinates $$$(x, y)$$$ of the point obtained as a result of sequentially executing all instructions (for example, N decreases $$$y$$$ by 1, S increases $$$y$$$ by 1, E increases $$$x$$$ by 1, W decreases $$$x$$$ by 1). Consider the following cases:
• $$$x \bmod 2 \neq 0$$$ or $$$y \bmod 2 \neq 0$$$. Obviously, a solution does not exist.
• $$$x = 0, y = 0, |S| = 2$$$. This is one of the strings NS, SN, WE, EW. Again, in this case, it is impossible to construct a solution, as both the rover and the helicopter must execute at least 1 instruction.
• $$$x = 0, y = 0, |S| > 2$$$. A solution exists: assign the first instruction to the helicopter, as well as one of its complements, which exists. Assign all the remaining positive number of instructions to the rover. Both will obviously end up at $$$(0, 0)$$$.
• All other cases: a solution exists. Assign $$$|x|/2$$$ and $$$|y|/2$$$ instructions moving in the direction of the sign of $$$x$$$ and $$$y$$$ respectively — which definitely exist — to the helicopter, and the rest to the rover. Both subsets of instructions will be non-empty.