#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
int n;
std::vector<int> parent_or_size;
DSU() : n(0) {}
DSU(int n) : n(n), parent_or_size(n, -1) {}
// int leader(int a) {
// return parent_or_size[a] < 0
// ? a
// : parent_or_size[a] = leader(parent_or_size[a]);
// }
int leader(int a) {
int x = a;
while (parent_or_size[x] >= 0)
x = parent_or_size[x];
while (a != x) {
int p = parent_or_size[a];
parent_or_size[a] = x;
a = p;
}
return x;
}
bool same(int a, int b) { return leader(a) == leader(b); }
int size(int a) { return -parent_or_size[leader(a)]; }
int merge(int a, int b) {
a = leader(a), b = leader(b);
if (a == b)
return a;
// if (-parent_or_size[a] < -parent_or_size[b])
// std::swap(a, b);
parent_or_size[a] += parent_or_size[b];
parent_or_size[b] = a;
return a;
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(n), group_size(n);
for (int i = 0; i < n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(n);
for (int i = 0; i < n; i++)
result[i].reserve(group_size[i]);
for (int i = 0; i < n; i++)
result[leader_buf[i]].push_back(i);
result.erase(
std::remove_if(result.begin(), result.end(),
[](const std::vector<int> &v) { return v.empty(); }),
result.end());
return result;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int R, S;
cin >> R >> S;
vector<vector<int>> grid(R, vector<int>(S));
for (int i = 0; i < R; i++)
for (int j = 0; j < S; j++)
cin >> grid[i][j];
vector comp(R, vector<int>(S, -1));
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int comps = 0;
vector<int> color;
for (int i = 0; i < R; i++) {
for (int j = 0; j < S; j++) {
if (comp[i][j] != -1)
continue;
int col = grid[i][j];
queue<pair<int, int>> q;
q.push({i, j});
color.push_back(col);
comp[i][j] = comps;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (min(nx, ny) < 0 || nx >= R || ny >= S || comp[nx][ny] != -1 ||
grid[nx][ny] != col)
continue;
comp[nx][ny] = comps;
q.push({nx, ny});
}
}
comps++;
}
}
vector<vector<int>> g(comps);
for (int i = 0; i < R; i++) {
for (int j = 0; j < S; j++) {
int a = comp[i][j];
for (int d = 0; d < 4; d++) {
int nx = i + dx[d], ny = j + dy[d];
if (min(nx, ny) < 0 || nx >= R || ny >= S)
continue;
int b = comp[nx][ny];
if (a != b)
g[a].push_back(b);
}
}
}
for (int i = 0; i < comps; ++i) {
if (!g[i].empty()) {
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
}
}
DSU dsu(comps);
vector<int> seen(comps);
int timer = 1;
int Q;
cin >> Q;
const int CLEAN_THRESHOLD = 2000;
while (Q--) {
int r, s, c;
cin >> r >> s >> c;
--r;
--s;
int v = comp[r][s];
v = dsu.leader(v);
if (color[v] == c)
continue;
color[v] = c;
vector<int> n;
n.reserve(g[v].size());
for (int x : g[v])
n.push_back(x);
for (int id = 0; id < n.size(); ++id) {
int nn = n[id];
int u = dsu.leader(nn);
v = dsu.leader(v);
if (v == u)
continue;
if (color[u] == c) {
int a = dsu.leader(v);
int b = dsu.leader(u);
if (a == b)
continue;
if (g[a].size() < g[b].size())
swap(a, b);
int cur = ++timer;
for (int x : g[b]) {
int xr = dsu.leader(x);
if (xr == a || seen[xr] == cur)
continue;
seen[xr] = cur;
g[a].push_back(xr);
n.push_back(xr);
}
g[b].clear();
int r = dsu.merge(a, b);
color[r] = c;
v = r;
if (g[a].size() > CLEAN_THRESHOLD) {
sort(g[a].begin(), g[a].end());
g[a].erase(unique(g[a].begin(), g[a].end()), g[a].end());
}
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < S; j++) {
int v = dsu.leader(comp[i][j]);
cout << color[v] << " \n"[j == S - 1];
}
}
return 0;
}
