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
Fisierul 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 iesire
Fisierul de iesire cutie.out va contine N linii, fiecare linie continand exact N caractere, reprezentand configuratia cutiei dupa executarea celor K rotatii.

Restrictii
1 <= N <= 1000
1 <= K <= 500 000

Exemplu

Timp maxim de executie/test: 0.5 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com