#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), rank.assign(n, 1); for (int i = 0; i < n; ++i) p[i] = i; nbr.resize(n), val.resize(n, 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) { int nr = fset(u); if (nr != x) nbr[x][v.first].insert(nr), nbr[nr][v.first].erase(y), nbr[nr][v.first].insert(x); } for (auto& pr : nbr[x]) pr.second.erase(x); nbr[y].clear(); } }; 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) dsu.val[dsu.fset(i * m + j)] = a[i][j]; for (auto x : bad) { int u = dsu.fset(x[0] * m + x[1]); int v = dsu.fset(x[2] * m + x[3]); dsu.nbr[u][a[x[2]][x[3]]].insert(v); dsu.nbr[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); int onode = node; if (dsu.val[node] == v) continue; dsu.val[node] = v; auto it1 = dsu.nbr[node].find(v); if (it1 == dsu.nbr[node].end()) continue; auto nbrs = it1->second; for (const auto& x : nbrs) if (dsu.val[dsu.fset(x)] == v) dsu.uset(node, x), node = dsu.fset(node); auto it2 = dsu.nbr[node].find(v); if (it2 == dsu.nbr[node].end()) continue; for (int nr : nbrs) { int rroot = dsu.fset(nr); for (auto it = dsu.nbr[rroot][v].begin(); it != dsu.nbr[rroot][v].end(); ) { int valr = dsu.fset(*it); if (valr != rroot) { it = dsu.nbr[rroot][v].erase(it); dsu.nbr[dsu.fset(valr)][v].insert(rroot); } else ++it; } dsu.nbr[rroot][v].erase(onode); } it2->second.clear(); } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) cout << dsu.val[dsu.fset(i * m + j)] << " "; cout << '\n'; } }