#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 777;
int N, Q, Ans[MAX_N][MAX_N];
char F[MAX_N][MAX_N][30];
int choose(int x, int y, int l, int d, int u) {
char f = F[x][y][l*9+d*3+u];
return (f == 'L' ? l : (f == 'D' ? d : u));
}
int cut(int v, int minV, int maxV) {
return min(max(v, minV), maxV);
}
void getAns(int xa, int xb, int ya, int yb, vector<int> &in, vector<int> &ch);
void change(int xa, int xb, int ya, int yb, vector<int> &pin, vector<int> &pch, int ps, int st) {
int n = xb - xa, m = yb - ya, s = n + m + 2;
vector<int> in(s*s, 0), ch(s*s, 0);
for(int i=0; i<ps; i++) for(int j=i; j<ps; j++) if(pin[i*ps+j]) {
int pc = pch[i*ps+j], pci = pc/ps, pcj = pc%ps;
int ni = cut(pci-st, 0, s-1), nj = cut(pcj-st, 0, s-1);
in[ni*s + nj] += pin[i*ps+j];
//printf("plus [%d %d] + %d(%d %d)\n", ni, nj, pin[i*ps+j], i, j);
}
getAns(xa, xb, ya, yb, in, ch);
for(int i=0; i<ps; i++) for(int j=i; j<ps; j++) if(pin[i*ps+j]) {
int pc = pch[i*ps+j], pci = pc/ps, pcj = pc%ps;
int ni = cut(pci-st, 0, s-1), nj = cut(pcj-st, 0, s-1);
int c = ch[ni*s + nj], ci = c/s, cj = c%s;
int npci = pci - ni + ci, npcj = pcj - nj + cj;
pch[i*ps+j] = npci*ps + npcj;
//printf("[%d %d] => [%d %d]\n", pci, pcj, npci, npcj);
}
}
void getAns(int xa, int xb, int ya, int yb, vector<int> &in, vector<int> &ch) {
int n = xb - xa, m = yb - ya, s = n + m + 2;
for(int i=0; i<s; i++) for(int j=i; j<s; j++) ch[i*s+j] = i*s+j;
//printf("%d %d | %d %d :\n", xa, xb, ya, yb);
//for(int i=0; i<s; i++) for(int j=i; j<s; j++) if(in[i*s+j]) printf("%d %d : %d\n", i, j, in[i*s+j]);
if(n == 0 || m == 0) return;
if(n == 1 && m == 1) {
int val[3];
for(int i=0; i<s; i++) for(int j=i; j<s; j++) if(in[i*s+j]) {
for(int k=0; k<3; k++) val[k] = (k<i ? 0 : (k<j ? 1 : 2));
Ans[xa][ya] += in[i*s+j] * val[1];
val[1] = choose(xb, yb, val[0], val[1], val[2]);
int cnt[2] = {0, 0};
for(int k=0; k<3; k++) if(val[k] < 2) cnt[val[k]]++;
cnt[1] += cnt[0];
ch[i*s+j] = cnt[0]*s + cnt[1];
}
return;
}
int xm = (xa + xb) >> 1, ym = (ya + yb) >> 1;
change(xa, xm, ya, ym, in, ch, s, xb-xm);
change(xa, xm, ym, yb, in, ch, s, xb-xm+ym-ya);
change(xm, xb, ya, ym, in, ch, s, 0);
change(xm, xb, ym, yb, in, ch, s, ym-ya);
}
int main() {
cin >> N >> Q;
for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) {
if(i < N && j < N) scanf("%s", F[i][j]);
else for(int k=0; k<27; k++) F[i][j][k] = 'U';
}
int s = 2*N+2;
vector<int> in(s*s, 0), ch(s*s, 0);
while(Q--) {
int x, y, z; scanf("%d%d%d", &x, &y, &z);
x++; y+=x;
in[x*s+y]++;
}
getAns(0, N, 0, N, in, ch);
for(int i=0; i<N; i++, puts("")) for(int j=0; j<N; j++) printf("%d ", Ans[i][j]+1);
return 0;
}
