#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]);
}
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<set<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].emplace(b);
}
}
}
for (int a = 0; a < comps; a++)
for (int b : g[a])
g[b].emplace(a);
DSU dsu(comps);
int Q;
cin >> Q;
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);
for (int x : g[b]) {
int xr = dsu.leader(x);
if (xr == a)
continue;
g[a].emplace(xr);
auto it = g[xr].find(b);
if (it != g[xr].end()) {
g[xr].erase(it);
g[xr].emplace(a);
} else {
g[xr].emplace(a);
}
if (xr != b)
n.push_back(xr);
}
g[b].clear();
int r = dsu.merge(a, b);
color[r] = c;
v = r;
}
}
}
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;
}
