Î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:
a) numărul de roboţi rămaşi după execuţia celor m comenzi,
b) 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 roboti1.in conţine pe prima linie numerele naturale p q separate printr-un spaţiu, reprezentând numărul de linii şi de coloane ale zonei. Pe a doua linie se află numărul natural n, reprezentând numărul de roboţi. Pe următoarele n linii se află câte trei valori separate prin câte un spaţiu, reprezentând linia, coloana şi orientarea fiecărui robot. Pe următoarea linie se află numărul natural 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 roboti1.out va conţine pe prima linie numărul de roboţi rămaşi în final. Pe linia a doua se va scrie 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
1<= p, q, m <= 50
2<= n <= 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ă.
Exemple
roboti1.in
roboti1.out
Explicaţii
4 4
3
1 1 E
1 3 V
4 4 S
2
FL
FF
FF
0
1 2 2
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ă.