masina

Vasile a "imprumutat" o masina si a plecat in oras sa se distreze. Ghinionul a fost ca masina apartinea politiei si era dotata cu un echipament care emitea semnale indicand directia de miscare a masinii.
Politistii au luat imediat harta orasului si, cunoscand pozitia initiala a masinii si directiile de miscare, vor sa determine pozitia finala a masinii.
Harta orasului este de forma dreptunghiulara, pe ea fiind marcate cu '.' (punct) pozitiile prin care masinile pot circula, iar cu 'X' pozitiile prin care masinile nu pot circula. Pozitia initiala a masinii a fost marcata pe harta cu '*'. Masina se poate deplasa in 4 directii la nord (adica mai sus), la sud (mai jos), la vest (adica la stanga) sau la est (la dreapta).

Cerinta

Pe prima linie a fisierului de intrare masina.in se gasesc doua numere naturale separate prin spatiu R C, unde R reprezinta numarul de linii, iar C numarul de coloane de pe harta orasului.
Fiecare dintre urmatoarele R linii contine o secventa de C caractere care pot fi doar '.', '*' sau 'X', descriind harta orasului.
Urmatoarea linie (a (R+2)-a) contine un numar natural N reprezentand numarul de schimbari de directie pe care le-a facut masina.
Fiecare dintre urmatoarele N linii contine un sir de caractere care poate fi (NORD, SUD, VEST sau EST). Evident, oricare doua directii consecutive sunt diferite.

Date de iesire

Fisierul de iesire masina.out contine harta orasului reprezentata ca in fisierul de intrare (R linii de cate C caractere). Pe harta vor fi marcate cu '*' numai pozitiile finale posibile ale masinii.

Restrictii

• 1<=R, C, <=50
• 1<=N<=1000

Exemple

masina.in	masina.out
3 4 .... *..X X.X. 2 EST NORD	.**. ...X X.X.