#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int n, Q, Sx[710][710], Sy[710][710];
char p[710][710][28];
struct A{
int a, b, c;
A operator +(const A &x){
A t;
t.a = a+x.a, t.b = b+x.b, t.c = c+x.c;
return t;
}
A operator -(const A &x){
A t;
t.a = a-x.a, t.b = b-x.b, t.c = c-x.c;
return t;
}
};
A Start(A x, int num){
A t;
t.a = min(x.a, num);
t.b = min(x.b, num - t.a);
t.c = min(x.c, num - t.a - t.b);
return t;
}
A End(A x, int num){
A t;
t.c = min(x.c, num);
t.b = min(x.b, num - t.c);
t.a = min(x.a, num - t.c - t.b);
return t;
}
int Num(A x){
int cnt = x.a + x.b + x.c;
return x.a * (cnt+cnt+3-x.a) / 2 + x.b;
}
void Addx(int x, int by, int ey, A tp, int c){
Sx[x][by + tp.a]+=c;
Sx[x][by + tp.a + tp.b]+=c;
Sx[x][by + tp.a + tp.b + tp.c]-= c*2;
}
void Addy(int y, int bx, int ex, A tp, int c){
Sy[bx][y]+=2*c;
Sy[bx + tp.c][y]-=c;
Sy[bx + tp.c + tp.b][y]-= c;
}
void Add(A *tp, int k, int ck){
if(k == 0)tp->a += ck;
else if(k == 1)tp->b += ck;
else tp->c += ck;
}
void Do(int bx, int by, int ex, int ey, vector<A> &ret, vector<int>C){
int i, j, k, cnt = ex-bx+ey-by+1, mx, my, cnt2, sz, pv;
A tp, tp2, tp3, tp4, tp5, tres;
ret.resize((cnt+1)*(cnt+2)/2);
if(bx == ex){
for(i=0;i<=cnt;i++){
for(j=0;j<=cnt - i;j++){
k = cnt-i-j;
tp.a=i,tp.b=j,tp.c=k;
ret[Num(tp)] = tp;
}
}
return;
}
if(by == ey){
for(i=0;i<=cnt;i++){
for(j=0;j<=cnt - i;j++){
k = cnt-i-j;
tp.a=i,tp.b=j,tp.c=k;
ret[Num(tp)] = tp;
}
}
return;
}
if(bx + 1 == ex && by + 1 == ey){
int t, tw[3], l, pv = 0;
for(i=0;i<=3;i++){
for(j=0;j<=3-i;j++){
k = 3-i-j;
tp.a=i,tp.b=j,tp.c=k;
tp2 = tp;
for(l=0;l<i;l++)tw[l]=0;
for(l=i;l<i+j;l++)tw[l]=1;
for(l=i+j;l<3;l++)tw[l]=2;
Add(&tp2, tw[1], -1);
t = p[ex][ey][tw[0]*9+tw[1]*3+tw[2]];
if(t == 'L')Add(&tp2, tw[0], 1);
if(t == 'D')Add(&tp2, tw[1], 1);
if(t == 'U')Add(&tp2, tw[2], 1);
ret[Num(tp)] = tp2;
Addx(ex, ey, ey, tp2 - Start(tp2, 1) - End(tp2, 1), C[pv]);
pv++;
}
}
return;
}
mx = (bx + ex + 1)>>1, my = (by + ey + 1)>>1;
vector<int>CNT;
vector<A>res, res2, res3, res4;
cnt2 = mx-bx+my-by+1;
sz = (cnt2+1)*(cnt2+2)/2;
CNT.resize(sz);
res.resize(sz);
res2.resize(sz);
res3.resize(sz);
res4.resize(sz);
pv = 0;
for(i=0;i<=cnt;i++){
for(j=0;j<=cnt-i;j++){
k = cnt - i -j;
tp.a = i,tp.b = j, tp.c =k;
tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
CNT[Num(tp2)]+=C[pv];
pv++;
}
}
Do(bx,by,mx,my, res, CNT);
for(i=0;i<sz;i++)CNT[i]=0;
pv = 0;
for(i=0;i<=cnt;i++){
for(j=0;j<=cnt-i;j++){
k = cnt - i -j;
tp.a = i,tp.b = j, tp.c =k;
tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
tp = Start(tp, ex-mx) + Start(res[Num(tp2)], my - by + 1);
CNT[Num(tp)] += C[pv];
pv++;
}
}
Do(mx,by,ex,my,res2, CNT);
for(i=0;i<sz;i++)CNT[i]=0;
pv = 0;
for(i=0;i<=cnt;i++){
for(j=0;j<=cnt-i;j++){
k = cnt - i - j;
tp.a = i,tp.b = j, tp.c = k;
tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
tp = End(res[Num(tp2)], mx - bx + 1) + End(tp, ey-my);
CNT[Num(tp)] += C[pv];
pv++;
}
}
Do(bx,my,mx,ey,res3, CNT);
for(i=0;i<sz;i++)CNT[i]=0;
pv = 0;
for(i=0;i<=cnt;i++){
for(j=0;j<=cnt-i;j++){
k = cnt - i - j;
tp.a = i,tp.b = j, tp.c = k;
tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
tp3 = Start(tp, ex-mx) + Start(res[Num(tp2)], my - by + 1);
tp4 = End(res[Num(tp2)], mx - bx + 1) + End(tp, ey-my);
tp = End(res2[Num(tp3)], ex - mx + 1) + Start(res3[Num(tp4)], ey - my + 1) - Start(res3[Num(tp4)], 1);
CNT[Num(tp)] += C[pv];
pv++;
}
}
Do(mx,my,ex,ey,res4, CNT);
pv = 0;
for(i=0;i<=cnt;i++){
for(j=0;j<=cnt-i;j++){
k = cnt - i - j;
tp.a = i,tp.b = j, tp.c = k;
tp2 = tp - Start(tp, ex-mx) - End(tp, ey-my);
tp3 = Start(tp, ex-mx) + Start(res[Num(tp2)], my - by + 1);
tp4 = End(res[Num(tp2)], mx - bx + 1) + End(tp, ey-my);
tp5 = End(res2[Num(tp3)], ex - mx + 1) + Start(res3[Num(tp4)], ey - my + 1) - Start(res3[Num(tp4)], 1);
tres = Start(res2[Num(tp3)], my - by) + res4[Num(tp5)] + End(res3[Num(tp4)], mx - bx);
ret[Num(tp)] = tres;
pv++;
}
}
}
int main(){
int i, j, a, b, c;
scanf("%d%d",&n,&Q);
for(i=2;i<=n;i++){
for(j=2;j<=n;j++){
scanf("%s",p[i][j]);
}
}
A tp;
vector<A> ret;
vector<int> C;
C.resize((n+n)*(n+n+1)/2);
while(Q--){
scanf("%d%d%d",&a,&b,&c);
tp.a = a, tp.b = b, tp.c = c;
C[Num(tp)]++;
Addy(1, 1, n, Start(tp, n), 1);
Addx(1, 2, n, End(tp, n-1), 1);
}
Do(1, 1, n, n, ret, C);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)Sx[i][j]+=Sx[i][j-1];
for(i=1;i<=n;i++)for(j=1;j<=n;j++)Sy[i][j]+=Sy[i-1][j];
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%d ",Sx[i][j]+Sy[i][j]+1);
}
printf("\n");
}
}
