311360: CF1974D. Ingenuity-2

D. Ingenuity-2time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

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

Output

RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH

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.

题目大意：
假设火星表面是一个无限坐标平面。初始时，毅力号-2探测车和智慧号-2直升机位于坐标点(0, 0)。为它们专门开发了一套由n个指令组成的指令集s，指令类型如下：
- N：向北移动一米（从点(x, y)到(x, y + 1)）；
- S：向南移动一米（从点(x, y)到(x, y - 1)）；
- E：向东移动一米（从点(x, y)到(x + 1, y)）；
- W：向西移动一米（从点(x, y)到(x - 1, y)）。

每个指令必须由探测车或直升机执行。此外，每个设备必须至少执行一个指令。你的任务是分配指令，使得在执行所有n个指令后，直升机和探测车最终到达同一个点，或者确定这是不可能的。

输入数据格式：
第一行输入包含t（1 ≤ t ≤ 10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 * 10^5）——指令的数量。
每个测试用例的第二行包含一个长度为n的字符串s，由字符'N'、'S'、'E'、'W'组成——指令序列。
保证所有测试用例的n之和不超过2 * 10^5。

输出数据格式：
对于每个测试用例，如果存在所需的指令分配，则输出一个长度为n的字符串p，由字符'R'、'H'组成。如果第i个操作应由探测车执行，则p_i='R'，如果第i个操作应由直升机执行，则p_i='H'。如果有多个解决方案，输出其中任何一个。
否则，输出NO。题目大意： 假设火星表面是一个无限坐标平面。初始时，毅力号-2探测车和智慧号-2直升机位于坐标点(0, 0)。为它们专门开发了一套由n个指令组成的指令集s，指令类型如下： - N：向北移动一米（从点(x, y)到(x, y + 1)）； - S：向南移动一米（从点(x, y)到(x, y - 1)）； - E：向东移动一米（从点(x, y)到(x + 1, y)）； - W：向西移动一米（从点(x, y)到(x - 1, y)）。 每个指令必须由探测车或直升机执行。此外，每个设备必须至少执行一个指令。你的任务是分配指令，使得在执行所有n个指令后，直升机和探测车最终到达同一个点，或者确定这是不可能的。 输入数据格式： 第一行输入包含t（1 ≤ t ≤ 10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 * 10^5）——指令的数量。 每个测试用例的第二行包含一个长度为n的字符串s，由字符'N'、'S'、'E'、'W'组成——指令序列。 保证所有测试用例的n之和不超过2 * 10^5。 输出数据格式： 对于每个测试用例，如果存在所需的指令分配，则输出一个长度为n的字符串p，由字符'R'、'H'组成。如果第i个操作应由探测车执行，则p_i='R'，如果第i个操作应由直升机执行，则p_i='H'。如果有多个解决方案，输出其中任何一个。 否则，输出NO。