O translație tr ∈ {N, E, S, 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 ∈ {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: tr1, rot1, tr2, rot2 …, trN, rotN în urma cărora ajunge la el acasă, în punctul de coordonate (a, b).

Cerința

1. Date fiind N, șirul de translații tr1, tr2, …, trN, precum și șirul de rotații rot1, rot2 …, rotN, să se determine coordonatele casei lui Gigel (a, b).
2. Date fiind N, șirul de translații tr1, tr2, …, trN, precum și coordonatele casei lui Gigel (a, b), să se determine dacă există un șir de rotații rot1, rot2 …, rotN 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 tr1, tr2, …, trN, precum și coordonatele casei lui Gigel (a, b), să se determine un șir de rotații rot1, rot2 …, rotN 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

Fișierul de intrare este rotatii.in. Prima linie va conține numărul cerinței C ∈ {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 tr1 tr2 … trN iar a patra linie va conține șirul de rotații rot1 rot2 … rotN 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 tr1 tr2 … trN, 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 tr1tr2 … trN, iar a patra linie va conține coordonatele casei lui Gigel a și b, separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire este rotatii.out. În funcție de numărul cerinței C ∈ {1, 2, 3}:

• Dacă C = 1, se vor afișa pe o singură linie coordonatele casei lui Gigel a și b, separate printr-un spațiu.
• 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.
• Dacă C = 3, se va afișa pe o singură linie șirul de rotații rot1, rot2 …, rotN, elementele consecutive fiind separate prin câte un spațiu.

Restricții și precizări

• C ∈ {1, 2, 3}
• 1 ≤ N ≤ 100.000
• tri ∈ {N, S, E, V} pentru 1 ≤ i ≤ N
• Dacă C = 1, atunci roti ∈ {0, 90, 180, 270} pentru 1 ≤ i ≤ N
• Dacă C = 2, atunci 1 ≤ T ≤ 10
• Dacă C ∈ {2, 3}, atunci -100.000 ≤ a, b ≤ 100.000
• Pentru 29 de puncte, roti = 0, pentru 1 ≤ i ≤ N
• Pentru 27 de puncte, C = 1
• Pentru 9 puncte, C = 2
• Pentru 12 puncte, C = 3 și N ≤ 100
• Pentru 9 puncte, C = 3 și N ≤ 1000
• Pentru 14 puncte, C = 3

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 = [N,N,S,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 N 0 N 270 S 90 V 90.
Astfel, traseul său este ilustrat și în figura de mai jos:

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, 90] convine, deci răspunsul este DA.
3. În al treilea scenariu, succesiunea de translații N N N N E 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] 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 = [S, S, S, S, 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ă.