#include<iostream> #include<vector> #include<map> #include<set> using namespace std; struct DSU { vector<int> p, rank, val; vector<map<int, set<int>>> nbr; DSU(int n) { p.resize(n + 1), rank.assign(n + 1, 1); for (int i = 0; i <= n; ++i) p[i] = i; nbr.resize(n + 1), val.resize(n + 1, 0); } int fset(int x) { return p[x] = (p[x] == x ? x : fset(p[x])); } bool iset(int x, int y) { return fset(x) == fset(y); } void uset(int x, int y) { x = fset(x), y = fset(y); if (x == y) return; if (rank[x] < rank[y]) swap(x, y); p[y] = x, rank[x] += rank[y]; for (auto v : nbr[y]) for (auto u : v.second) nbr[x][v.first].insert(u); } }; int di[] = { 0, 0, -1, 1 }; int dj[] = { 1, -1, 0, 0 }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)), bad; for (auto& x : a) for (auto& y : x) cin >> y; DSU dsu(n * m); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (int d = 0; d < 4; ++d) { int ni = di[d] + i; int nj = dj[d] + j; if ((ni < 0) || (nj < 0) || (nj >= m) || (ni >= n)) continue; if (a[ni][nj] == a[i][j]) dsu.uset(i * m + j, ni * m + nj); else bad.push_back({ i, j, ni, nj }); } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { int node = i * m + j; if (dsu.p[node] == node) dsu.val[node] = a[i][j]; } for (auto x : bad) { int u = x[0] * m + x[1]; int v = x[2] * m + x[3]; dsu.nbr[dsu.fset(u)][a[x[2]][x[3]]].insert(v); dsu.nbr[dsu.fset(v)][a[x[0]][x[1]]].insert(u); } int q; cin >> q; while (q--) { int i, j, v; cin >> i >> j >> v; --i, --j; int node = dsu.fset(i * m + j); dsu.val[node] = v; for (auto x : dsu.nbr[node][v]) if (dsu.val[dsu.fset(x)] == v) dsu.uset(node, x), node = dsu.fset(node); } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int node = i * m + j; cout << dsu.val[dsu.fset(node)] << " "; } cout << '\n'; } }