Mirror Cupa SEPI Seniori | Desen

Odată ce și-a dat seama că desenatul "intersecției de meteoriți" este o treabă futilă, FlaviuS a descoperit că o ocupație mult mai complicată și importantă este întocmai opusul! El are un plan de atac: știe unde pune pixul pe hârtie, și intocmai care este șirul de direcții pe care îl va parcurge (Nord, Est, Sud și Vest). Scopul lui este de a crea o linie frântă care nu trece de $2$ ori prin același punct, mai puțin punctul final, care vrea să fie întocmai același cu cel inițial. De asemenea, $2$ mutări consecutive au orientări axiale diferite (după una verticală urmează una orizontală și vice-versa).

Cerință

Date fiind $T$ desene înfățișate prin $N$ și șirul de $N$ direcții, FlaviuS vă roagă (nu știe soluția) să îi spuneți dacă își poate îndeplini visul artistic, iar dacă da, cât de lung trebuie să fie fiecare segment pe care acesta îl desenează.

Date de intrare

Pe prima linie se află numărul $T$ de desene pe care FlaviuS vrea să le finalizeze cu succes. Fiecare dintre cele $T$ teste este descris prin $2$ linii, prima având numărul natural $N$, iar a doua, un șir de $N$ caractere din mulțimea $\{\texttt{N}, \texttt{E}, \texttt{S}, \texttt{W}\}$.

Date de ieșire

Pentru fiecare test, pe prima linie se va afișa YES dacă desenul poate fi realizat, respectiv NO altfel. Dacă se poate, pe a doua linie se vor afișa $N$ numere naturale nenule care reprezintă lungimea liniei în fiecare direcție.

Restricții și precizări

• $1 \leq T \leq 2 \ 000 \ 000$.
• $1 \leq N \leq 200 \ 000$.
• Suma valorilor $N$ dintr-un fișier nu va depăși $2 \ 000 \ 000$.
• Fiecare valoare de $N$ este pară, iar primul caracter este E sau W.
• Orice soluție corectă în care lungimile sunt cel mult $10^9$ este acceptată.
• Orice soluție care nu afișează, pentru răspuns afirmativ, $N$ numere pozitive mai mici sau egale cu $10^9$ se va acorda $0\%$ din punctajul pe test.
• Dacă se determină corect existența unei soluții, dar valorile din șir nu creează un desen pe placul lui FlaviuS, se va acorda $20\%$ din punctajul pe test.

Exemplu

stdin

3
6
ENWNWS
6
ENWNEN
20
ENESENWNENWNWSWSWSES

stdout

YES
4 1 3 3 1 4
NO
YES
2 3 2 3 2 6 3 2 3 1 1 1 4 1 1 2 2 3 2 4

Explicație

Pentru primul exemplu, desenul este redat în imaginea de mai jos. Bulina albastră indică de unde începe și se termină capodopera.

Pentru al doilea exemplu, nu există nicio soluție corectă.

Pentru al treilea exemplu, drumul următor nu este deloc suspicios.