Fișierul intrare/ieșire	cutie.in, cutie.out	Sursă	.campion 2007
Autor	Emanuela Cerchez	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.5 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Cutie

Multi copii sunt familiarizati cu un joc in care o biluta este plasata intr-o cutie patrata in care sunt diferite obstacole, astfel incat interiorul cutiei are aspectul unui labirint. Tinand cutia vertical, bila poate cadea (sub influenta gravitatiei) pana la marginea cutiei sau pana la intalnirea unui obstacol.
Cutia poate fi rotita cu 90 de grade (in sensul acelor de ceas sau invers). Ca urmare, sub influenta gravitatiei, din nou bila se va deplasa pana la intalnirea unui obstacol sau a marginilor cutiei.

Cutia jocului poate fi reprezentata ca o matrice cu N linii si N coloane. Daca elementul de pe linia i si coloana j este un obstacol el va fi marcat in matrice cu litera X, iar daca este culoar, va fi marcat in matrice cu . (punct). Pozitia bilei va fi marcata in matrice cu litera B.

Cerinta

Scrieti un program care sa determine configuratia cutiei dupa o secventa de rotatii specificata.

Date de intrare

Fișierul de intrare cutie.in contine pe prima linie doua numere naturale separate prin spatiu N K, unde N reprezinta dimensiunea cutiei, iar K reprezinta numarul de rotatii. Pe urmatoarele N linii sunt scrise cate N caractere, reprezentand configuratia initiala a cutiei. Pe urmatoarele K linii sunt scrise rotatiile, cate o rotatie pe o linie. O rotatie este descrisa prin litera S daca rotatia se face cu 90 de grade in sensul invers acelor de ceas, sau prin litera D daca rotatia se realizeaza cu 90 de grade in sensul acelor de ceas.

Date de ieșire

Fișierul de ieșire cutie.out va contine N linii, fiecare linie continand exact N caractere, reprezentand configuratia cutiei dupa executarea celor K rotatii.

Restricții

• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ 500 000

Exemplu