← 返回题目列表

Codeforces · 1974/D

D. 独创性-2

中文机器翻译题面 查看原题

让我们将火星表面想象为一个无限的坐标平面。最初,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,解决方案是不可能的。