Направления

Дана строка $s$ длины $n$, состоящая из букв $S$, $E$, $N$, $W$. Каждая буква представляет направление движения на координатной плоскости. Начав с точки $(0,0)$, вы выполняете последовательность из $n$ шагов, как описано в строке $s$. Правила движения для каждого направления следующие:

• Если $s[i]=\text{’E’}$, переместитесь из точки $(x,y)$ в точку $(x+l_E,y)$.

• Если $s[i]=\text{’W’}$, переместитесь из точки $(x,y)$ в точку $(x-l_W,y)$.

• Если $s[i]=\text{’N’}$, переместитесь из точки $(x,y)$ в точку $(x,y+l_N)$.

• Если $s[i]=\text{’S’}$, переместитесь из точки $(x,y)$ в точку $(x,y-l_S)$.

За одну операцию вам разрешается изменить любой символ в строке $s$ на его противоположный:

• $E\leftrightarrow W$, $N\leftrightarrow S$.

Определите, возможно ли выполнить некоторые операции (возможно, ноль) перед движением так, чтобы, завершив все $n$ шагов, вы вернулись в начальную точку $(0,0)$.

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

Первая строка содержит целое число $t$ $(1\le t\le 10^5)$ — количество наборов входных данных в одном файле.

Каждый набор описывается в двух строках. Первая строка содержит целые числа $n,l_E,l_W,l_N,l_S$ $(1\le n\le 5\cdot 10^5,1\le l_E,l_W,l_N,l_S\le 10^9)$.

Вторая строка содержит строку $s$ длины $n$ $(s_i\in \{E,W,N,S\})$.

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

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

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

Вы можете выводить YES и NO в любом регистре (например, строки yES, yes и Yes будут распознаны как положительный ответ).

Примеры

Примечание

В первом случае мы можем за одну операцию изменить строку на WNSE. Давайте смоделируем наши движения, описанные этой строкой:

1. После первого шага мы находимся в точке $(0-1,0)=(-1,0)$;

2. После второго шага мы находимся в точке $(-1,0+1)=(-1,1)$;

3. После третьего шага мы находимся в точке $(-1,1-1)=(-1,0)$;

4. После четвертого шага мы находимся в точке $(-1+1,0)=(0,0)$.

Таким образом, мы вернулись в начальную точку.

В третьем случае мы можем изменить строку на EWW, чтобы вернуться в начальную точку.

Можно доказать, что во втором и четвертом случаях невозможно изменить строку так, чтобы после завершения всех шагов мы вернулись в $(0,0)$.

Оценивание

1. ($2$ балла): $n\le 2$;

2. ($4$ балла): $l_E=l_W=l_N=l_S=1$;

3. ($10$ баллов): $n\le 10,t\le 1000$;

4. ($10$ баллов): $n\le 3000,t\le 10^4$;

5. ($14$ баллов): $l_E,l_W,l_N,l_S\le 10^3$;

6. ($10$ баллов): без дополнительных ограничений;