Напрямки

Вам дано рядок $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$ балів): без додаткових обмежень;