ape

Mihai crede că mă pricep la informatică şi mă roagă să îl ajut la efectuarea unor calcule. Mi-a povestit că în vacanţă a fost la ţară la bunici. Bunicii lui se ocupă de piscicultură şi au preluat spre utilizare o zonă de teren unde se află lacuri, heleştee şi bălţi. Sunt plătite taxe speciale în funcţie de suprafeţele acestor ape.

Bunicului i se pare că cei de la oficiul unde se plătesc taxele au date greşite în dosare, despre ariile acestor suprafeţe de apă şi l-a rugat pe Mihai să îi calculeze cu aproximaţie aceste arii. Mihai a studiat problema şi s-a hotărât să înconjoare fiecare apă, mergând pe conturul acesteia.

Pasul lui are lungimea de 1 metru. La fiecare pas Mihai foloseşte o busolă şi îşi notează într-un carneţel direcţia înspre care a fost efectuat pasul $Nord, Sud, Est$ sau $Vest$. După fiecare pas Mihai actualizează şi numărul de paşi pe care i-a făcut.

Cerință

Se doreşte să se afle, pentru fiecare traseu:

1. Dimensiunile pe direcţiile $Vest - Est$ şi respectiv $Nord - Sud$ ale unei suprafeţe dreptunghiulare de arie minimă care cuprinde în interior sau pe margini suprafaţa apei;
2. Sensul în care a fost parcurs traseul: $0$-pentru sens orar, respectiv $1$-pentru sens invers orar;
3. Aria suprafeţei apei înconjurate, din interiorul traseului.

Date de intrare

Fişierul de intrare ape.in are pe prima linie numărul $P$ de paşi ai traseului. În linia $2$ se află un şir de $P$ litere mari, fără spaţii între ele, din mulţimea $\{ N,S,E,V \}$ reprezentând traseul.

Date de ieșire

Fişierul de ieşire ape.out va conţine patru numere naturale separate prin câte un spaţiu: primul număr reprezintă dimensiunea pe direcţia $Vest - Est$ şi al doilea număr reprezintă dimensiunea pe direcţia $Nord – Sud$ a suprafeţei dreptunghiulare de arie minimă care cuprinde în interior sau pe margini suprafaţa apei delimitată de traseu; al treilea număr reprezintă sensul parcurgerii, iar al patrulea număr reprezintă aria.

Restricții și precizări

• $1 \leq P \leq 10 \ 000$
• Pentru $30$% din teste traseele vor avea lungimea maximă $2 \ 000$
• Dacă dimensiunile suprafeţei dreptunghiulare de arie minimă sunt corecte, atunci se va acorda $10\%$ din punctaj/test
• Dacă sensul traseului este determinat corect, atunci se vor primi $10\%$ puncte/test
• Aria suprafeţei apei este un număr natural nenul

Exemplu

ape.in

16
NNVVSVSSESEEENNV

ape.out

3 3 1 5

Explicație

Căsuţele marcate cu $-$ reprezintă traseul, iar pătratele maro reprezintă apa

Zona mărginită de linia îngroşată reprezintă suprafaţa dreptunghiulară minimală ce conţine pătratele maro, care reprezintă apa

Căsuţa marcată cu $*$ este poziţia de pornire