Problem 946: pelican

Î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$ ) $\rarr$ ( $0, 3$ ) $\rarr$ ( $4, 3$ ) $\rarr$ ( $3, 3$ ).
$R \ nr$ – Raţa se roteşte cu $nr \cdot 90 \degree$ în sens orar, unde $nr \in {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$ mod $N$ , păstrând orientarea. Se garantează că $nr / N \in \{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ță

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$ 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 \leq N \leq 1 \ 000$ ;
$1 \leq P \leq 10 \ 000$ ;
$1 \leq K \leq 100 \ 000$ ;
$0 \leq i, j < N$ ; şi $1 \leq d \leq 4$ ;
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 \leq 100$ , $P \leq 100$ şi $K \leq 1 000$ .
Pentru teste valorând $36$ de puncte $N > 100$ , $1 \ 000 \leq P \leq 5 000$ ; şi $K \leq 50 \ 000$ .