roboti

Într-o zonă dreptunghiulară cu $p$ linii şi $q$ coloane se află $n$ roboţi. Celula din stânga sus se află pe linia $1$ şi coloana $1$. Pentru fiecare robot se cunoaşte linia şi coloana pe care se află, precum şi orientarea lui. Un robot poate fi orientat în una din cele patru direcţii: nord, sud, est sau vest, codificate cu caracterele N, S, E, respectiv V. Fiecare robot execută $m$ comenzi. O comandă este codificată printr-un caracter L, R sau F. La o comandă de tip L, robotul se întoarce cu $90$ de grade spre stânga, în sensul invers acelor de ceasornic. La o comandă de tip R, robotul se întoarce cu $90$ de grade spre dreapta, în sensul acelor de ceasornic. La o comandă de tip F, robotul se deplasează cu o poziţie în sensul în care este orientat robotul.
Roboţii execută simultan prima comandă din şirul lor de comenzi, apoi a doua comandă, etc.
Dacă la un moment dat, doi sau mai mulţi roboţi ajung în aceeaşi poziţie, aceasta va conduce la dispariţia lor, iar celula din care dispar se consideră traversată de toţi cei care au dispărut.
Dacă un robot se deplasează în afara suprafeţei la execuţia unei comenzi, robotul dispare.
Se consideră trecere printr-o celulă vizitarea rezultată în urma executării unei comenzi de tip F. Dacă un robot trece de mai multe ori printr-o celulă, se contorizează fiecare trecere a sa. Celula din care pleacă fiecare robot se consideră trecere pentru robotul respectiv.

Cerinţă

Scrieţi un program care să determine:

1. numărul de roboţi rămaşi după execuţia celor $m$ comenzi
2. poziţia celulei din zonă prin care s-a trecut cel mai des (dacă există mai multe celule, atunci se va preciza cea cu indicele de linie cel mai mic, iar dacă există mai multe cu acest indice, cea cu indicele de coloană cel mai mic) şi numărul de treceri prin această celulă.

Date de intrare

Fişierul de intrare roboti.in conţine:

• pe prima linie: $p$ şi $q$, valori separate printr-un spaţiu şi reprezentând numărul de linii şi de coloane ale zonei
• pe a doua linie: valoarea $n$, reprezentând numărul de roboţi
• pe următoarele $n$ linii: câte trei valori separate prin câte un spaţiu, reprezentând linia, coloana şi orientarea fiecărui robot
• pe următoarea linie: valoarea $m$ reprezentând numărul de comenzi de executat de către fiecare robot;=
• pe următoarele $n$ linii se află câte $m$ caractere reprezentând comenzile pentru fiecare robot (mai întâi cele $m$ comenzi pentru primul robot, apoi cele $m$ comenzi pentru al doilea robot, ş.a.m.d.). Între caracterele unei comenzi nu există nici un spaţiu

Date de ieşire

Fişierul de ieşire roboti.out va conţine:

• pe prima linie numărul de roboţi rămaşi în final
• pe linia a doua poziţia celulei (linie şi coloană) prin care s-a trecut cel mai des (dacă există mai multe celule, atunci se va preciza cea cu indicele de linie cel mai mic, iar dacă există mai multe cu acest indice, cea cu indicele de coloană cel mai mic) şi numărul de treceri prin această celulă, trei valori separate prin câte un spaţiu

Restricţii şi precizări

• $1 \leq p, q, m \leq 50$
• $2 \leq n \leq 50$
• Caracterele cu care se codifică orientările pot fi doar N, S, E, V, iar cele pentru comenzi L, R sau F (litere mari).
• Iniţial, nu există doi sau mai mulţi roboţi în aceeaşi celulă.
• Se acordă $50\%$ din punctaj pentru rezolvarea cerinţei $1$ şi $50\%$ pentru cerinţa $2$.

Exemplu

roboti.in

4 4
3
1 1 E
1 3 V
4 4 S
2
FL
FF
FF

roboti.out

0
1 2 2

Explicaţie

După prima comandă, roboţii $1$ şi $2$ ar trebui să ajungă în aceeaşi celulă, deci dispar. Al treilea robot conform primei deplasări va părăsi zona, deci dispare. În final vor fi $0$ roboţi. Doi roboţi au ajuns în celula de pe linia $1$ şi coloana $2$, după care au dispărut. Prin celelalte celule s-a trecut maxim o singură dată.