#include <iostream>
#include <string>
#include <vector>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
using namespace std;
string S[705][705];
int ans[705][705];
vector<vector<pii>> f(int lx, int rx, int ly, int ry, vector<vector<int>> cnt)
{
int m = rx - lx + ry - ly + 1;
vector<vector<pii>> ret(m + 1);
for(int i = 0; i <= m; ++i) ret[i].resize(i + 1);
if(lx == rx || ly == ry)
for(int i = 0; i <= m; ++i) for(int j = 0; j <= i; ++j) ret[i][j] = {i, j};
else if(m == 3)
{
for(int i = 0; i <= 3; ++i)
{
for(int j = 0; j <= i; ++j)
{
int arr[3];
if(j >= 1) arr[0] = 0; else if(i >= 1) arr[0] = 1; else arr[0] = 2;
if(j >= 2) arr[1] = 0; else if(i >= 2) arr[1] = 1; else arr[1] = 2;
if(j >= 3) arr[2] = 0; else if(i >= 3) arr[2] = 1; else arr[2] = 2;
char c = S[ly][lx][arr[0] * 9 + arr[1] * 3 + arr[2]];
if(c == 'L') arr[1] = arr[0];
if(c == 'U') arr[1] = arr[2];
pii tmp = {0, 0};
if(arr[0] == 0) ++tmp.ff, ++tmp.ss; else if(arr[0] == 1) ++tmp.ff;
if(arr[1] == 0) ++tmp.ff, ++tmp.ss; else if(arr[1] == 1) ++tmp.ff;
if(arr[2] == 0) ++tmp.ff, ++tmp.ss; else if(arr[2] == 1) ++tmp.ff;
ans[ly][lx] += arr[1] * cnt[i][j];
ret[i][j] = tmp;
}
}
}
else
{
int mx = lx + rx >> 1, my = ly + ry >> 1;
int A = mx - lx, B = rx - mx, C = my - ly, D = ry - my;
vector<vector<pii>> conv(m + 1);
for(int i = 0; i <= m; ++i) conv[i].resize(i + 1);
for(int i = 0; i <= m; ++i) for(int j = 0; j <= i; ++j) conv[i][j] = {i, j};
int m1 = A + C + 1;
vector<vector<int>> c1(m1 + 1);
for(int i = 0; i <= m1; ++i) c1[i].resize(i + 1);
for(int i = 0; i <= m; ++i)
for(int j = 0; j <= i; ++j)
c1[max(0, min(i, m - B) - D)][max(0, min(j, m - B) - D)] += cnt[i][j];
auto q1 = f(lx, mx, ly, my, c1);
for(int i = 0; i <= m; ++i)
{
for(int j = 0; j <= i; ++j)
{
int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
if(x < D || x > m - B) _x = x;
else _x = D + q1[max(0, min(x, m - B) - D)][max(0, min(y, m - B) - D)].ff;
if(y < D || y > m - B) _y = y;
else _y = D + q1[max(0, min(x, m - B) - D)][max(0, min(y, m - B) - D)].ss;
conv[i][j] = {_x, _y};
}
}
vector<vector<int>>().swap(c1);
vector<vector<pii>>().swap(q1);
int m2 = B + C + 1;
vector<vector<int>> c2(m2 + 1);
for(int i = 0; i <= m2; ++i) c2[i].resize(i + 1);
for(int i = 0; i <= m; ++i)
{
for(int j = 0; j <= i; ++j)
{
int x = conv[i][j].ff, y = conv[i][j].ss;
c2[max(0, x - A - D)][max(0, y - A - D)] += cnt[i][j];
}
}
auto q2 = f(mx, rx, ly, my, c2);
for(int i = 0; i <= m; ++i)
{
for(int j = 0; j <= i; ++j)
{
int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
if(x < A + D) _x = x;
else _x = A + D + q2[max(0, x - A - D)][max(0, y - A - D)].ff;
if(y < A + D) _y = y;
else _y = A + D + q2[max(0, x - A - D)][max(0, y - A - D)].ss;
conv[i][j] = {_x, _y};
}
}
vector<vector<int>>().swap(c2);
vector<vector<pii>>().swap(q2);
int m3 = A + D + 1;
vector<vector<int>> c3(m3 + 1);
for(int i = 0; i <= m3; ++i) c3[i].resize(i + 1);
for(int i = 0; i <= m; ++i)
{
for(int j = 0; j <= i; ++j)
{
int x = conv[i][j].ff, y = conv[i][j].ss;
c3[min(x, m - B - C)][min(y, m - B - C)] += cnt[i][j];
}
}
auto q3 = f(lx, mx, my, ry, c3);
for(int i = 0; i <= m; ++i)
{
for(int j = 0; j <= i; ++j)
{
int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
if(x > m - B - C) _x = x;
else _x = q3[min(x, m - B - C)][min(y, m - B - C)].ff;
if(y > m - B - C) _y = y;
else _y = q3[min(x, m - B - C)][min(y, m - B - C)].ss;
conv[i][j] = {_x, _y};
}
}
vector<vector<int>>().swap(c3);
vector<vector<pii>>().swap(q3);
int m4 = B + D + 1;
vector<vector<int>> c4(m4 + 1);
for(int i = 0; i <= m4; ++i) c4[i].resize(i + 1);
for(int i = 0; i <= m; ++i)
{
for(int j = 0; j <= i; ++j)
{
int x = conv[i][j].ff, y = conv[i][j].ss;
c4[max(0, min(x, m - C) - A)][max(0, min(y, m - C) - A)] += cnt[i][j];
}
}
auto q4 = f(mx, rx, my, ry, c4);
for(int i = 0; i <= m; ++i)
{
for(int j = 0; j <= i; ++j)
{
int x = conv[i][j].ff, y = conv[i][j].ss, _x, _y;
if(x < A || x > m - C) _x = x;
else _x = A + q4[max(0, min(x, m - C) - A)][max(0, min(y, m - C) - A)].ff;
if(y < A || y > m - C) _y = y;
else _y = A + q4[max(0, min(x, m - C) - A)][max(0, min(y, m - C) - A)].ss;
conv[i][j] = {_x, _y};
}
}
// cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << endl;
// for(auto i : cnt) { for(auto j : i) cout << j << ' '; cout << endl; }
vector<vector<int>>().swap(c4);
vector<vector<pii>>().swap(q4);
ret = conv;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, n; cin >> m >> n;
for(int i = 1; i < m; ++i) for(int j = 1; j < m; ++j) cin >> S[i][j];
vector<vector<int>> cnt(2 * m);
for(int i = 0; i < 2 * m; ++i) cnt[i].resize(i + 1);
int tmp[2 * m]{};
for(int i = 0; i < n; ++i)
{
int x, y, z; cin >> x >> y >> z;
++cnt[x + y][x];
++tmp[x]; ++tmp[x + y];
}
for(int i = 1; i < 2 * m; ++i) tmp[i] += tmp[i - 1];
for(int i = 0; i < m; ++i) ans[m - i - 1][0] = tmp[i];
for(int i = 1; i < m; ++i) ans[0][i] = tmp[i + m - 1];
f(1, m, 1, m, cnt);
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < m; ++j)
cout << ans[i][j] + 1 << ' ';
cout << '\n';
}
return 0;
}
