让我们将火星表面想象为一个无限的坐标平面。最初,Perseverance-2 漫游车和 Ingenuity-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 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 指令数。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符“N”、“S”、“E”、“W”(指令序列)组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 5$$$。
输出
对于每个测试用例,如果存在所需的指令分布,则输出长度为 $$$n$$$ 的字符串 $$$p$$$,由字符 'R'、'H' 组成。如果第$$$i$$$操作应由流动站执行,则$$$p_i=\text{R}$$$,如果第$$$i$$$操作应由直升机执行,则$$$p_i=\text{H}$$$。如果有多个解,输出任意一个。
否则,输出NO。
示例
输入 #1
10 6 NENSNE 3 WWW 6 NESSWS 2 SN 2 WE 4 SSNN 4 WESN 2 SS 4 EWNN 4 WEWE
输出 #1
RRHRRH NO HRRHRH NO NO RHRH RRHH RH RRRH RRHH
注意
让我们考虑第一个示例:字符串 $$$S = \texttt{NENSNE}$$$。如下图所示,一种可能的解决方案是 $$$p = \texttt{RRHRRH}$$$,使用它,漫游车和直升机最终都会向北一米,向东一米。
对于WWW,解决方案是不可能的。