Tărâm

Pentru a-și afla destinul, aventurierul Lionel își propune să ajungă la Muntele Destinului, folosindu-se de o hartă străveche, alcătuită din $N^2$ celule dispuse pe câte $N$ linii și câte $N$ coloane numerotate de la $1$. Astfel, acesta pornește dintr-o celulă specificată cu coordonatele $(X_{start}, Y_{start})$ și se deplasează inițial în direcția $D$.
Conform legendei hărții, fiecare celulă poate reprezenta: fie un drum sigur $(‘.’)$ care permite deplasarea rapidă, păduri dense $(‘P’)$ ce necesită timp dublu pentru traversare, și mlaștini $(‘M’)$ ce blochează complet avansul.
Instrucțiunile de pe hartă determină mișcarea lui Lionel astfel:

Simbolul $(‘R’)$ schimbă direcția de mers a lui Lionel, întorcându-l la ultima celulă în care a existat o schimbare de direcție și rotind direct, ia acesteia cu $90^{\circ}$ în sensul acelor de ceasornic (nord devine est, nord-est devine sud-est, est devine sud etc. conform diagramei din dreapta).

Date de intrare

Fișierul de intrare taram.in va conține pe prima linie $4$ numere întregi separate prin câte un spațiu: $N$ (dimensiunea hărții), $(X_{start}, Y_{start})$ (coordonatele celulei inițiale de unde Lionel își va începe aventura) și $D$ (direcția inițială de deplasare).
Următoarele $N$ linii descriu legenda hărții inițiale, fiecare linie fiind alcătuită din câte $N$ caractere.
Linia $N + 2$ va conține un număr întreg reprezentând numărul de operații suplimentare $T$.
În funcție de tipul operației, următoarele $T$ linii vor conține un număr întreg $K$ (tipul operației), urmat de:

• Un număr întreg $X$, în cazul în care $K = 1$, reprezentând numărul de ore în urma căruia Lionel este curios să afle coordonatele celulei în care se află, pornind din celula de coordonate $(X_{start}, Y_{start})$ ș deplasându-se în direcția $D$.
• Două numere întregi separate prin câte un spațiu $X, Y$ dacă $K = 2$, reprezentând coordonatele celulei în care se va plasa un simbol de rotire $(‘R’)$.

Date de ieșire

Fișierul de ieșire taram.out va conține răspunsurile la cele $T$ operații suplimentare în felul următor:

• Pentru o operație de tip $1$, se va afișa pe un rând coordonatele celulei în care Lionel se află după cele $X$ ore, și numărul de ore pe care acesta l-a petrecut acolo, la momentul $X$.
• Pentru o operație de tip $2$ nu se va afișa nimic.

Restricții și precizări

• $1 \leq N \leq 1 \ 100$
• $1 \leq T \leq 200$
• Coordonatele unei celule se vor afișa separate prin virgulă și între paranteze rotunde.
• Celula de coordonate $(Xstart, Ystart)$ din care Lionel își începe aventura este o celulă de tip drum $(‘.’)$.
• Direcția inițială de deplasare $D$ va lua una din valorile $N$, $S$, $E$, $V$, $W$, $X$, $Y$, $Z$, acestea având aceeași însemnătate ca cele definite în cerința problemei.
• Pentru o operație de tip $2$, celula de coordonate $(X, Y)$ pe care se va plasa un simbol de rotire $(‘R’)$ este o celulă de tip drum $(‘.’)$.
• În momentul în care Lionel întâlnește o celulă de tip rotire $(’R’)$, el va revizita, pe rând, toate celulele pe care le-a vizitat pe drumul de la ultima schimbare de direcție la celula de tip rotire $(’R’)$.
• Pentru teste în valoare de $5$ puncte, nu vor exista operații de tipul $2$.
• Pentru alte teste în valoare de $10$ puncte, $N \leq 500$.
• Pentru alte teste în valoare de $85$ de puncte, nu există restricții suplimentare.

Exemplul 1

taram.in

5 1 1 S
.N.MM
...MD
W..M.
.ENPN
.PPPP
4
1 4
2 1 3
1 14
1 25

taram.out

(1,3) 0
(4,3) 0
(2,5) 6

Exemplul 2

taram.in

5 4 5 N
.E.DZ
.P...
..PX.
..XV.
N...X
4
1 25
2 3 1
2 2 1
1 10

taram.out

(1,1) 13
(3,1) 0

Explicații

Lionel incepe de pe pozitia $(1, 1)$ și ajunge în celula $(1, 3)$, dupa $4$ ore conform instrucțiunii $W$.
Plasând un $R$ pe poziția $(1, 3)$, rezultă că instrucțiunea de pe poziția $(3, 1) = W$ devine, de fapt, $Y$. Astfel, acesta va parcurge coordonatele $(3, 1) \rightarrow (2, 2) \rightarrow (1, 3)$, după care se întoarce, aflând că ultima instrucțiune a fost falsă $(1, 3) \rightarrow (2, 2) \rightarrow (3, 1)$. Lionel își continuă drumul până cand ajunge din nou pe poziția $(1, 3)$, urmărând traseul $(3, 1) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (3, 3) \rightarrow (2, 3) \rightarrow (1, 3)$ de unde rezultă că instrucțiunea de pe poziția $(4, 3) = N$ devine, de fapt $E$.
Traseul complet pentru a ajunge la Muntele Destinului este: $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 2) \rightarrow (3, 1) \rightarrow (4, 2) \rightarrow (4, 3) \rightarrow (3, 3) \rightarrow (2, 3) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (4, 3) \rightarrow (4, 4) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (2, 5)$.