#include<cstdio>
#include<vector>
char a[707][707][33];
int r[707][707];
int val(const char,const int,const int,const int);
void cal(const int,const int,const int,const int,const int,const int,const std::vector<int>&,std::vector<int>&);
void dnc(const int,const int,const int,const int,const std::vector<int>&,std::vector<int>&);
int main()
{
std::vector<int> in,out;
int i,j,n,m;
scanf("%d%d",&n,&m);
for(i=1;i<n;i++)for(j=1;j<n;j++)scanf("%s",a[i][j]);
in.resize(4*(n+1)*(n+1));
out.resize(4*(n+1)*(n+1));
while(m--)
{
scanf("%d%d%*s",&i,&j);
i++;
j+=i;
in[i*2*(n+1)+j]++;
}
dnc(0,0,n+1,n+1,in,out);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)printf("%d ",r[i][j]+1);
puts("");
}
}
int val(const char c,const int l,const int d,const int u)
{
return c=='L'?l:c=='D'?d:u;
}
void cal(const int sx,const int sy,const int ex,const int ey,const int of,const int sz,const std::vector<int> &in,std::vector<int> &out)
{
int i,x,y,z,tsz;
std::vector<int> tin,tout;
tsz=ex+ey-sx-sy;
tin.resize(tsz*tsz);
tout.resize(tsz*tsz);
for(i=0;i<sz*sz;i++)if(in[i])
{
x=std::min(std::max(out[i]/sz-of,0),tsz-1);
y=std::min(std::max(out[i]%sz-of,0),tsz-1);
tin[x*tsz+y]+=in[i];
}
dnc(sx,sy,ex,ey,tin,tout);
for(i=0;i<sz*sz;i++)if(in[i])
{
x=out[i]/sz-of;
y=out[i]%sz-of;
if(x>=0&&x<tsz)
{
if(y>=0&&y<tsz)
{
z=tout[x*tsz+y];
x=z/tsz;
y=z%tsz;
}
else x=tout[x*tsz+tsz-1]/tsz;
}
else if(y>=0&&y<tsz)y=tout[y]%tsz;
out[i]=(x+of)*sz+(y+of);
}
}
void dnc(const int sx,const int sy,const int ex,const int ey,const std::vector<int> &in,std::vector<int> &out)
{
int i,sz;
sz=ex+ey-sx-sy;
for(i=0;i<sz*sz;i++)out[i]=i;
if(ex-sx<2||ey-sy<2)return;
if(ex-sx==2&&ey-sy==2)
{
int x,y,z;
for(i=0;i<sz*sz;i++)if(in[i])
{
x=(i<4)+((i&3)<1);
y=(i<8)+((i&3)<2);
z=(i<12)+((i&3)<3);
r[sx][sy]+=in[i]*y;
y=val(a[sx+1][sy+1][x*9+y*3+z],x,y,z);
out[i]=(((x<1)+(y<1)+(z<1))<<2)|((x<2)+(y<2)+(z<2));
}
return;
}
int tx,ty;
std::vector<int> tin,tout;
tx=(sx+ex)/2;
ty=(sy+ey)/2;
sz=ex+ey-sx-sy;
cal(sx,sy,tx+1,ty+1,ex-tx-1,sz,in,out);
cal(sx,ty,tx+1,ey,ex+ty-tx-sy-1,sz,in,out);
cal(tx,sy,ex,ty+1,0,sz,in,out);
cal(tx,ty,ex,ey,ty-sy,sz,in,out);
}
