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
- Date fiind
N, șirul de translațiitr1,tr2, …,trN, precum și șirul de rotațiirot1,rot2…,rotN, să se determine coordonatele casei lui Gigel(a, b). - Date fiind
N, șirul de translațiitr1,tr2, …,trN, precum și coordonatele casei lui Gigel(a, b), să se determine dacă există un șir de rotațiirot1,rot2…,rotNastfel î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 daTscenarii independente, iar voi va trebui să rezolvați problema separat și să răspundeți (afirmativ sau negativ) pentru fiecare dintre celeTscenarii în parte. - Date fiind
N, șirul de translațiitr1,tr2, …,trN, precum și coordonatele casei lui Gigel(a, b), să se determine un șir de rotațiirot1,rot2…,rotNastfel î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ărulN, a treia linie va conține șirul de translații sub forma unui șir de caractere nedespărțite prin spațiitr1tr2…trNiar a patra linie va conține șirul de rotațiirot1rot2…rotNsub forma unui șir de numere în care elementele consecutive sunt separate prin câte un spațiu. - Dacă
C = 2, atunci urmeazăTscenarii de rezolvat. Fiecare scenariu este descris pe trei linii. Prima linie va conține numărulN, a doua linie va conține șirul de translații sub forma unui șir de caractere nedespărțite prin spațiitr1tr2…trN, iar a treia linie va conține coordonatele casei lui Gigelașib, separate printr-un spațiu. - Dacă
C = 3, atunci a doua linie va conține numărulN, a treia linie va conține șirul de translații sub forma unui șir de caractere nedespărțite prin spațiitr1tr2…trN, iar a patra linie va conține coordonatele casei lui Gigelașib, 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 Gigelașib, separate printr-un spațiu. - Dacă
C = 2, se vor afișaTlinii, câte una pentru fiecare scenariu. Fiecare linie va conține unul dintre mesajeleDAsauNU, reflectând răspunsul (afirmativ sau negativ) pentru scenariul respectiv. - Dacă
C = 3, se va afișa pe o singură linie șirul de rotațiirot1,rot2…,rotN, elementele consecutive fiind separate prin câte un spațiu.
Restricții și precizări
C ∈ {1, 2, 3}1 ≤ N ≤ 100.000tri∈ {N, S, E, V}pentru1 ≤ i ≤ N- Dacă
C = 1, atunciroti∈ {0, 90, 180, 270}pentru1 ≤ i ≤ N - Dacă
C = 2, atunci1 ≤ T ≤ 10 - Dacă
C ∈ {2, 3}, atunci-100.000 ≤ a, b ≤ 100.000 - Pentru 29 de puncte,
roti= 0, pentru1 ≤ i ≤ N - Pentru 27 de puncte,
C = 1 - Pentru 9 puncte,
C = 2 - Pentru 12 puncte,
C = 3șiN ≤ 100 - Pentru 9 puncte,
C = 3șiN ≤ 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ă.