CF1974D.Ingenuity-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 \times 10^5$），表示指令的数量。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 'N'、'S'、'E'、'W' 组成，表示指令序列。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，如果存在满足条件的指令分配方案，输出一个长度为 $n$ 的字符串 $p$，由字符 'R' 和 'H' 组成。如果第 $i$ 条操作应由探测车执行，则 $p_i = \text{R}$；如果应由直升机执行，则 $p_i = \text{H}$。如果有多种方案，输出任意一种即可。

如果不存在满足条件的分配方案，输出 NO。

我们来看第一个示例：字符串 $S = \texttt{NENSNE}$。一种可能的方案（如下图所示）是 $p = \texttt{RRHRRH}$，使用该方案后，探测车和直升机都将停在北一米、东一米的位置。

对于 WWW，这种分配方案是不可能的。

由 ChatGPT 4.1 翻译