C. Камушки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Под влиянием праздничной атмосферы Сайтама подарил Геносу два клеточных пути длины n (странненький подарок, даже для Сайтамы). Клеточный путь — это упорядоченная последовательность соседних клеток на бесконечной сетке. Две клетки называются соседними, если у них есть общая сторона.

Например, клеточный путь может выглядеть так: (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 1) → (0, 1) → ( - 1, 1). Обратите внимание, что клетки в этой последовательности могут повторяться, то есть путь может иметь самопересечения.

Перемещение вдоль пути разрешено только в соседние клетки пути. Таким образом, из i-й позиции можно перейти только в (i - 1)-ю или (i + 1)-ю клетки. Обратите внимание, что из первой и последней ячеек клетчатого пути есть только один возможный ход. Дополнительно обратите внимание, что даже если j-я клетка пути совпадает с i-й, то всё равно можно произвести ходы только в (i - 1)-ю и (i + 1)-ю клетки. Например, из второй клетки приведённого выше пути можно пойти только в первую и третью клетки.

Чтобы перемещение всегда определялось однозначно, в каждом из путей никогда не имеют повторяется одна и та же клетка на отрезке длины три. Например, в правильном клеточном пути не может быть подотрезка вида (0, 0) → (0, 1) → (0, 0)

На первую клетку каждого клеточного пути кладётся по камушку. Генос хочет, чтобы оба камушка докатились до последней ячейки каждого клеточного пути, но всё не так просто. Каждый раз, когда Генос двигает один из камушков, второй камушек копирует его движение, если это возможно. Например, если один камушек движется на восток, то тогда другой камушек постарается тоже двигаться на восток. Под постарается имеется в виду, что если движение на восток возможно, то камушек сделает такое перемещение.

Движение на север соответствует увеличению второй координаты на 1, а движение на юг — её уменьшению на 1. Аналогично движение на восток увеличивает первую координату на 1, а движение на запад уменьшает её на 1.

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

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

В первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 1 000 000) — длина путей.

Во второй строке входных данных записана строка, состоящая из n - 1 символа (каждый из которых равен 'N', 'E', 'S', или 'W') — клеточный путь первого камешка. Символы можно рассматривать как последовательность ходов, необходимых, чтобы пройти этот сеточный путь. Так примеру из условия соответствует последовательность "NNESWW".

В третьей строке входных данных записана строка из (n - 1)-го символа (каждый из которых равен 'N', 'E', 'S', либо 'W') — клеточный путь второго камешка.

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

Выведите "YES" (без кавычек), если можно добиться того, чтобы оба камушка одновременно находились на конечных клетках своих путей. В противном случае выведите "NO" (без кавычек).

Примеры
Входные данные
7
NNESWW
SWSWSW
Выходные данные
YES
Входные данные
3
NN
SS
Выходные данные
NO
Примечание

В первом примере, первый путь соответствует описанному в условии. Оба шарика могу оказаться в концах своих путей после следующей последовательности действий: NNESWWSWSW.

Во втором примере, переместить оба шарика в концы соответствующих путей невозможно.