Rezolvare PBinfo #4082

Într-o minunată zi de primăvară, P răţuşte au ieşit la plimbare pe lac. Un pelican milităros, care stătea pe mal, a decis să facă instrucţie cu nevinovatele raţe. Pentru aceasta, a cartografiat imediat lacul şi l-a reprezentat ca o matrice cu N linii (numerotate de la 0 la N-1 de sus în jos) şi N coloane (numerotate de la 0 la N-1 de la stânga la dreapta). Astfel, poziţia oricărei raţe pe lac poate fi identificată prin linia şi coloana pe care se află raţa. Raţele sunt orientate cu faţa spre una dintre direcţiile Nord, Sud, Est, Vest. Pelicanul a codificat direcţiile 1, 2, 3, 4 ca în figură.

Când pelicanul strigă: “Comanda la mine!” raţele trebuie să execute simultan cele K comenzi pe care le dă pelicanul. Comenzile pelicanului sunt codificate astfel:

• A nr – Raţa avansează cu nr poziţii în direcţia spre care este orientată. Dacă avansând depăşeşte marginea tablei de joc va intra pe latura opusă. De exemplu, pe un lac 5 x 5, o raţă plasată în poziţia (1,3) cu orientare 1 (Nord), executând comanda A 3 se va deplasa astfel: (1,3) → (0,3) → (4,3) → (3,3).
• R nr – Raţa se roteşte cu nr • 90o în sens orar, unde nr ∈ {1,2,3,4}. De exemplu, dacă orientarea iniţială a raţei este 1 (Nord), comanda R 2 va schimba orientarea spre 3 (Sud).
• Z nr – Raţa zboară pe linia nr / N şi coloana nr % N, păstrând orientarea. Se garantează că nr / N ∈ {0,1, ..., N - 1}. De exemplu, pe un lac 5 x 5, după executarea comenzii Z 7, raţa va ajunge pe linia 1 şi coloana 2.

Cerința

Scrieţi un program care, cunoscând poziţia iniţială pe lac a celor P raţe şi succesiunea comenzilor pelicanului, determină poziţia finală a fiecărei raţe.

Date de intrare

Fișierul de intrare pelican.in conţine pe prima linie trei numere naturale N P K, cu semnificaţia din enunţ. Pe următoarele P linii sunt date câte 3 numere naturale i j d (0 ≤ i, j < N şi 1 ≤ d ≤ 4) cu semnificaţia că pe linia i şi coloana j se găseşte o raţă orientată în direcţia d. Ultimele K linii conţin cele K comenzi, câte o comandă pe o linie, în formatul specificat în enunţ (un caracter din mulţimea {'A', 'R', 'Z'} şi un număr natural). Valorile scrise pe aceeaşi linie sunt separate de câte un spaţiu.

Date de ieșire

Fișierul de ieșire pelican.out va conţine P linii. Pe linia i va fi scrisă poziţia celei de a i-a raţe din fişierul de intrare (linia şi coloana separate printr-un singur spaţiu) după executarea în ordine a celor K comenzi.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ P ≤ 10.000
• 1 ≤ K ≤ 100.000
• Mai multe raţe pot ocupa aceeaşi poziţie.
• Se garantează că datele din fişierul de intrare sunt corecte.
• Pentru teste valorând 76 de puncte fişierul de intrare nu conţine comanda Z.
• Pentru teste valorând 20 de puncte N ≤ 100, P ≤ 100 şi K ≤ 1000.
• Pentru teste valorând 36 de puncte N > 100, 1000 ≤ P ≤ 5000 şi K ≤ 50000.

Exemplu:

pelican.in

5 3 4
1 1 2
2 3 1
3 1 4
A 3
R 3
A 1
A 3

pelican.out

2 4
4 4
2 3

Explicație

Lacul are 5 linii şi 5 coloane. Pe lac există 3 raţe poziţionate ca în figură.

Pelicanul dă 4 comenzi pe care toate cele 3 raţe le execută în ordine. Raţele execută comanda A 3

Raţele execută comanda R 3 (se rotesc cu 270o în sens orar)

Raţele execută comanda A 1

Raţele execută comanda A 3