rotatii

O translație $tr \in \{\text{N}, \text{S}, \text{E}, \text{V}\}$ este o mișcare de o unitate într-unul dintre cele patru puncte cardinale: nord, sud, est sau vest. Similar, o rotație $rot \in \{0, 90, 180, 270\}$ este o rotație cu numărul corespunzător de grade în sensul acelor de ceasornic în jurul originii planului cartezian, adică punctului $(0, 0)$. Mai precis, plecând din punctul $(x, y)$ și aplicând fie o translație $tr$, fie o rotație $rot$, se ajunge într-un punct $(x', y')$ conform tabelelor de mai jos:

După o noapte furtunoasă, Gigel pleacă din crâșma satului, poziționată în punctul de coordonate $(0, 0)$ și efectuează în ordine o succesiune alternativă de translații și rotații: $tr_1, rot_1, tr_2, rot_2, \ldots, tr_N, rot_N$, în urma cărora ajunge la el acasă, în punctul de coordonate $(a, b)$.

Cerință

1. Date fiind $N$, șirul de translații $tr_1, \ldots, tr_N$, precum și șirul de rotații $rot_1, \ldots, rot_N$, să se determine coordonatele casei lui Gigel $(a, b)$.
2. Date fiind $N$, șirul de translații $tr_1, \ldots, tr_N$, precum și coordonatele casei lui Gigel $(a, b)$, să se determine dacă există un șir de rotații $rot_1, \ldots, rot_N$ astfel încât în urma efectuării succesiunii de translații și rotații Gigel să ajungă la el acasă. Doar pentru această cerință, se vor da $T$ scenarii independente, iar voi va trebui să rezolvați problema separat și să răspundeți (afirmativ sau negativ) pentru fiecare dintre cele $T$ scenarii în parte.
3. Date fiind $N$, șirul de translații $tr_1, \ldots, tr_N$, precum și coordonatele casei lui Gigel $(a, b)$, să se determine un șir de rotații $rot_1, \ldots, rot_N$ astfel încât în urma efectuării succesiunii de translații și rotații Gigel să ajungă la el acasă. Doar pentru această cerință, se garantează că un astfel de șir de rotații există. În caz că există mai multe șiruri de rotații posibile, se acceptă oricare.

Date de intrare

Prima linie va conține numărul cerinței $C \in \{1, 2, 3\}$. Doar pentru $C = 2$, prima linie va conține și numărul de scenarii de rezolvat $T$ (caz în care $C$ și $T$ sunt separate printr-un spațiu). În funcție de valoarea $C$, restul intrării este structurat după cum urmează:

• Dacă $C = 1$, atunci a doua linie va conține numărul $N$, a treia linie va conține șirul de translații sub forma unui șir de caractere nedespărțite prin spații $tr_1 tr_2 \ldots tr_N$, iar a patra linie va conține șirul de rotații $rot_1, rot_2, \ldots, rot_N$ sub forma unui șir de numere în care elementele consecutive sunt separate prin câte un spațiu.
• Dacă $C = 2$, atunci urmează $T$ scenarii de rezolvat. Fiecare scenariu este descris pe trei linii. Prima linie va conține numărul $N$, a doua linie va conține șirul de translații sub forma unui șir de caractere nedespărțite prin spații $tr_1 tr_2 \ldots tr_N$, iar a treia linie va conține coordonatele casei lui Gigel $a$ și $b$, separate printr-un spațiu.
• Dacă $C = 3$, atunci a doua linie va conține numărul $N$, a treia linie va conține șirul de translații sub forma unui șir de caractere nedespărțite prin spații $tr_1 tr_2 \ldots tr_N$, iar a patra linie va conține coordonatele casei lui Gigel $a$ și $b$, separate printr-un spațiu.

Date de ieșire

În funcție de numărul cerinței $C \in \{1, 2, 3\}$:

1. Dacă $C = 1$, se vor afișa pe o singură linie coordonatele casei lui Gigel $a$ și $b$, separate printr-un spațiu.
2. Dacă $C = 2$, se vor afișa $T$ linii, câte una pentru fiecare scenariu. Fiecare linie va conține unul dintre mesajele DA sau NU, reflectând răspunsul (afirmativ sau negativ) pentru scenariul respectiv.
3. Dacă $C = 3$, se va afișa pe o singură linie șirul de rotații $rot_1, rot_2, \ldots, rot_N$, elementele consecutive fiind separate prin câte un spațiu.

Restricții și precizări

• $C \in \{1, 2, 3\}$
• $1 \leq N \leq 100 \ 000$
• $tr_i \in \{\text{N}, \text{S}, \text{E}, \text{V}\}$ pentru $1 \leq i \leq N$.
• Dacă $C = 1$, atunci $rot_i \in \{0, 90, 180, 270\}$ pentru $1 \leq i \leq N$.
• Dacă $C = 2$, atunci $1 \leq T \leq 10$.
• Dacă $C \in \{2, 3\}$, atunci $-100 \ 000 \leq a, b \leq 100 \ 000$.

Exemplul 1

rotatii.in

1
4
NNSV
0 270 90 90

rotatii.out

2 2

Explicație

În acest test avem $C = 1$, $N = 4$, șirul de translații $tr = [\text{N}, \text{N}, \text{S}, \text{V}]$ și cel de rotații $rot = [0, 270, 90, 90]$. Gigel pleacă din $(0, 0)$ și execută în ordine succesiunea de translații și rotații $\text{N}, 0, \text{N}, 270, \text{S}, 90, \text{V}, 90$. Astfel, traseul său este:

$\displaystyle (0, 0) \xrightarrow{\text{N}} (0, 1) \xrightarrow{0} (0, 1) \xrightarrow{\text{N}} (0, 2) \xrightarrow{270} (-2, 0) \xrightarrow{\text{S}} (-2, -1) \xrightarrow{90} (-1, 2) \xrightarrow{\text{V}} (-2, 2) \xrightarrow{90} (2, 2)$

De unde deducem coordonatele casei sale $(a, b) = (2, 2)$.

Exemplul 2

rotatii.in

2 5
4
NNSV
2 2
4
NNSV
-2 2
6
NNNNEE
2 4
5
SSSSS
100 100
4
NNSV
-2 1

rotatii.out

DA
DA
DA
NU
NU

Explicație

În acest test avem $C = 2$ și $T = 5$ scenarii de rezolvat:

1. Primul scenariu corespunde situației din primul exemplu (șirul de rotații $rot = [0, 270, 90, 90]$ convine), deci răspunsul este DA.
2. Al doilea scenariu este asemănător primului: observăm că în traseul său, Gigel trece deja prin $(a, b) = (-2, 2)$ înainte de ultima rotație, deci este suficient să anulăm ultima rotație. Cu alte cuvinte, șirul de rotații $rot = [0, 270, 90, 0]$ convine, deci răspunsul este DA.
3. În al treilea scenariu, succesiunea de translații $\text{N}, \text{N}, \text{N}, \text{N}, \text{E}, \text{E}$ l-ar duce deja pe Gigel la el acasă, adică în punctul de coordonate $(a, b) = (2, 4)$. Prin urmare, șirul de rotații $rot = [0, 0, 0, 0, 0, 0]$ convine, și deci răspunsul este DA.
4. În al patrulea scenariu, casa lui Gigel se află în punctul de coordonate $(a, b) = (100, 100)$, care este prea departe de punctul de plecare $(0, 0)$ date fiind $N = 5$ și șirul de translații $tr = [\text{S}, \text{S}, \text{S}, \text{S}, \text{S}]$, indiferent ce șir de rotații am alege. Prin urmare, răspunsul pentru acest scenariu este NU.
5. În al cincilea scenariu, deși casa lui Gigel, aflată în punctul de coordonate $(a, b) = (-2, 1)$, nu este atât de departe de punctul de plecare, niciun șir de rotații nu convine, deci răspunsul este NU.

Exemplul 3

rotatii.in

3
4
NNSV
2 2

rotatii.out

0 270 90 90

Explicație

Acest test corespunde situației din primul exemplu, pentru care știm deja că șirul de rotații $rot = [0, 270, 90, 90]$ convine. Un alt răspuns posibil ar fi fost $rot = [0, 90, 90, 180]$. Orice răspuns corect se acceptă.