B. Абсолютно относительно
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Из окна Бенедикту видно площадку в парке, на которой участники кружка робототехники проводят тестовые испытания своих разработок. Сейчас маленькая платформа на колесиках должна была проехать по заданному маршруту, который был сформирован заранее.

Участник кружка, который составлял маршрут, задавал направление движения платформы относительно карты местности: команда $$$N$$$ означала движение на одну единицу расстояния вверх по карте, $$$S$$$ – вниз, $$$W$$$ — влево, $$$E$$$ — вправо.

Ориентация карты при этом не менялась. Будем называть эту карту неподвижной, а маршрут, проложенный по неподвижной карте — абсолютным.

Однако карта, которую использует платформа, связана с платформой. Это означает, что если платформа двигается, не меняя направления движения, она двигается в направлении $$$N$$$. Команда $$$S$$$ предписывает платформе выполнить разворот и переместиться на одну единицу расстояния в направлении, противоположном направлению, в котором платформа была ориентирована в предыдущий момент времени. Аналогично, команда $$$W$$$ предписывает платформе повернуть налево относительно её текущей ориентации и переместиться на одну единицу расстояния в новом направлении, а команда $$$E$$$ предписывает платформе повернуть относительно текущей ориентации направо и также переместиться на одну единицу расстояния в этом направлении.

Будем называть эту карту связанной с платформой, а маршрут, проложенный по связанной с платформой карте, — относительным.

В начальный момент времени платформа была ориентирована по направлению $$$N$$$ на неподвижной карте (иными словами, карта, связанная с платформой, совпадала с неподвижной картой).

Ваша задача — проложить относительный маршрут таким образом, чтобы при движении платформы он в точности совпал с абсолютным. Иными словами, нужно проложить маршрут по карте, связанной с платформой, так, чтобы после каждого шага платформа оказывалась в соответствующей точке маршрута на неподвижной карте, составленного участником кружка.

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

В первой строке содержится непустая последовательность символов $$$N$$$, $$$S$$$, $$$W$$$, $$$E$$$ (без пробелов) — абсолютный маршрут.

Количество символов в последовательности не превосходит $$$10^5$$$.

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

Выведите последовательность символов $$$N$$$, $$$S$$$, $$$W$$$, $$$E$$$ (той же длины, что и исходная) — относительный маршрут, совпадающий при движении платформы с абсолютным.

Система оценки

В каждой из двух подзадач этой задачи применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для второй подзадачи требуется, чтобы программа верно решала первую подзадачу. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
1до 3 (до 40)в абсолютном маршрутенетполная
используются только два
символа направления
24 (до 60)в абсолютном маршруте1полная
используются любые
символы направлений

Пример
Входные данные
NWSEESNW
Выходные данные
NWWWNESW
Примечание

Поясним приведённый пример.

Будем считать, что на неподвижной карте ось абсцисс направлена вправо, а ось ординат — вверх. Также будем считать, что изначально платформа располагается в точке $$$(0, 0)$$$.

Первая команда в абсолютном маршруте $$$N$$$, платформа должна переместиться в точку $$$(0, 1)$$$. Поскольку платформа изначально ориентирована по направлению $$$N$$$ неподвижной карты, то первой командой в относительном маршруте также будет команда $$$N$$$.

Вторая команда $$$W$$$ предписывает платформе повернуть налево и переместиться в точку $$$(-1, 1)$$$. В относительном маршруте для этого потребуется такая же команда $$$W$$$.

Третья команда $$$S$$$ предписывает платформе переместиться в точку $$$(-1, 0)$$$. Поскольку после выполнения второй команды платформа ориентирована по направлению $$$W$$$, то на карте, связанной с платформой, это вновь будет поворот налево, т.е. команда $$$W$$$.

Четвёртая команда $$$E$$$ предписывает платформе переместиться в точку $$$(0, 0)$$$. Для карты, связанной с платформой, это вновь будет поворот налево и команда $$$W$$$.

Пятая команда $$$E$$$ предписывает платформе переместиться в точку $$$(1, 0)$$$. Для карты, связанной с платформой, это движение в текущем направлении и команда $$$N$$$.

Шестая команда $$$S$$$ предписывает платформе переместиться в точку $$$(1, -1)$$$. Для карты, связанной с платформой, это поворот направо относительно текущего направления и команда $$$E$$$.

Седьмая команда $$$N$$$ предписывает платформе переместиться в точку $$$(1, 0)$$$. Для карты, связанной с платформой, это разворот в противоположном направлении и команда $$$S$$$.

Наконец, восьмая команда $$$W$$$ предписывает платформе переместиться в точку $$$(0, 0)$$$. Для карты, связанной с платформой, это поворот налево и (также) команда $$$W$$$.