年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车，但他没想到的是那辆车属于警察局，并且车上装有用于发射车子移动路线的装置。

那个装置太旧了，以至于只能发射关于那辆车的移动路线的方向信息。

编写程序，通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。

小镇的地图是矩形的，上面的符号用来标明哪儿可以行车哪儿不行。“.”表示小镇上那块地方是可以行车的，而符号“X”表示此处不能行车。拉尔夫所开小车的初始位置用字符的“*”表示，且汽车能从初始位置通过。

汽车能向四个方向移动：向北(向上)，向南(向下)，向西(向左)，向东(向右)。

拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向，拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。

输入文件的第一行包含两个用空格隔开的自然数R和C，1≤R≤50，1≤C≤50，分别表示小镇地图中的行数和列数。

以下的R行中每行都包含一组C个符号(“.”或“X”或“*”)用来描述地图上相应的部位。

接下来的第R+2行包含一个自然数N，1≤N≤1000，表示一组方向的长度。

接下来的N行幅行包含下述单词中的任一个：NORTH(北)、SOUTH(南)、WEST(西)和EAST(东)，表示汽车移动的方向，任何两个连续的方向都不相同。

输出文件应包含用R行表示的小镇的地图(象输入文件中一样)，字符“*”应该仅用来表示汽车最终可能出现的位置。

4 5

.....

.X...

...*X

X.X..

3

NORTH

WEST

SOUTH

.....

*X*..

*.*.X

X.X..

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<string>

#include<map>

using namespace std;

map<string,int>q;

string fx;

char xp[][];

int jz[][];

int w,stx,sty,p,i,j,r,v,n,xf[]={-,,,},yf[]={,,-,};

void wk(string s,int a,int b)

{

    ++w;

    while(a+xf[q[s]]>=&&a+xf[q[s]]<r&&b+yf[q[s]]>=&&b+yf[q[s]]<v&&jz[a+xf[q[s]]][b+yf[q[s]]]!=)

    {

        a+=xf[q[s]];b+=yf[q[s]];

        jz[a][b]=w;

    }

}

void wq(string b)

{

    i=-;j=-;

    while(i!=r)

    {

        i++;

        j=-;

        while(j!=v)

        {

            j++;

            if(jz[i][j]==w-)

            {

                int a=i,c=j;

                if(b=="SOUTH")

                {

                    while(a+>=&&a+<r&&jz[a+][c]!=)

                    {

                        jz[a+][c+]=w;

                        a=a+;

                    }

                }

                if(b=="NORTH")

                {

                    while(a->=&&a-<r&&jz[a-][c]!=)

                    {

                        jz[a-][c+]=w;

                        a=a-;

                    }

                }

                if(b=="WEST")

                {

                    while(c->=&&c-<v&&jz[a][c-]!=)

                    {

                        jz[a][c-]=w;

                        c=c-;

                    }

                }

                if(b=="EAST")

                {

                    while(c+>=&&c+<v&&jz[a][c+]!=)

                    {

                        jz[a][c+]=w;

                        c=c+;

                    }

                }

            }

        }

    }

}

int main()

{

    char ch;

    cin>>r>>v;

    for(i=;i<r;++i)

    {

        for(j=;j<v;++j)

        {

            cin>>xp[i][j];

            if(xp[i][j]=='*')

            {

                xp[i][j]='.';

                stx=i;

                sty=j;

            }

            if(xp[i][j]=='X')

            jz[i][j]=;

            else jz[i][j]=-;

        }

    }

    cin>>n;

    q["NORTH"]=;

    q["SOUTH"]=;

    q["WEST"]=;

    q["EAST"]=;

    for(int t=;t<n;++t)

    {

        if(t==)

        {

            cin>>fx;

            wk(fx,stx,sty);

        }

        else {

            cin>>fx;

            ++w;

            wq(fx);

        }

    }

    for(i=;i<r;++i)

    {

        for(j=;j<v;++j)

        {

            if(jz[i][j]==-) cout<<'.';

            else if(jz[i][j]==) cout<<'X';

            else if(jz[i][j]==w) cout<<"*";

            else cout<<".";

        }

        cout<<endl;

    }

    return ;

}