D. Ingenuity-2
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представим поверхность Марса как бесконечную координатную плоскость. Изначально в точке с координатой $$$(0, 0)$$$ находятся ровер Perseverance-2 и вертолёт Ingenuity-2. Специально для них был разработан набор инструкций $$$s$$$ из $$$n$$$ инструкций следующего вида:

  • 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$$$) — количество инструкций.

Вторая строка каждого набора содержит строку $$$s$$$ длины $$$n$$$ из символов 'N', 'S', 'E', 'W' — последовательность инструкций.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных теста не превосходит $$$2 \cdot 10 ^ 5$$$.

Выходные данные

Для каждого набора входных данных, если существует требуемое распределение инструкций, выведите строку $$$p$$$ длины $$$n$$$ из символов 'R', 'H'. Если $$$i$$$-я операция должна быть исполнена ровером, то $$$p_i=\text{R}$$$, если $$$i$$$-я операция должна быть исполнена вертолётом, то $$$p_i=\text{H}$$$. Если существует несколько решений, выведите любое из них.

В противном случае выведите NO.

Пример
Входные данные
10
6
NENSNE
3
WWW
6
NESSWS
2
SN
2
WE
4
SSNN
4
WESN
2
SS
4
EWNN
4
WEWE
Выходные данные
RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH
Примечание

Рассмотрим первый пример: строка $$$S = \texttt{NENSNE}$$$. Одно из возможных решений, показанное на рисунке ниже $$$p = \texttt{RRHRRH}$$$, с использованием которого и ровер, и вертолет окажутся на один метр на север и на один метр на восток.

Для WWW решение невозможно.