Представим поверхность Марса как бесконечную координатную плоскость. Изначально в точке с координатой \((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\) инструкций вертолёт и ровер оказались в одной точке или определить что это невозможно.
Выходные данные
Для каждого набора входных данных, если существует требуемое распределение инструкций, выведите строку \(p\) длины \(n\) из символов 'R', 'H'. Если \(i\)-я операция должна быть исполнена ровером, то \(p_i=\text{R}\), если \(i\)-я операция должна быть исполнена вертолётом, то \(p_i=\text{H}\). Если существует несколько решений, выведите любое из них.
В противном случае выведите NO.
Примечание
Рассмотрим первый пример: строка \(S = \texttt{NENSNE}\). Одно из возможных решений, показанное на рисунке ниже \(p = \texttt{RRHRRH}\), с использованием которого и ровер, и вертолет окажутся на один метр на север и на один метр на восток.
Для WWW решение невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|