#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define fi first #define se second #define vi vector<int> #define vll vector<long long> #define pii pair<int, int> #define pll pair<long long, long long> #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count()); inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);} inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);} #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; struct pair_hash{ size_t operator()(const pair<int,int>&x)const{ return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32)); } }; const int MAXN = 2e5 + 7; const int MAXM = 1e5 + 7; const int B = 667; int dx[4] = {0, 0, -1, 1}; int dy[4] = {1, -1, 0, 0}; vector<pii> pos[MAXN]; int col[MAXN]; int liczSpec[MAXM]; int idSpec[MAXM]; vi g[MAXN][MAXN / B + 10];//polączenia int licznik[MAXN]; int rep[MAXN][MAXN / B + 10]; int Rep[MAXN]; vector<vi> A; vector<vi> id; vi special; int n, m, k; int Find(int x, int a){ if(rep[x][a] == x){ return x; } return rep[x][a] = Find(rep[x][a], a); } int Find2(int x){ if(Rep[x] == x){ return x; } return Rep[x] = Find2(Rep[x]); } vi toAdd; void bfs(int a, int b){ queue<pii> q; q.push(mp(a, b)); while(sz(q)){ pii curr = q.front(); q.pop(); int x = curr.fi; int y = curr.se; pos[id[x][y]].pb(mp(x, y)); for(int z = 0; z < 4; z++){ int nx = x + dx[z]; int ny = y + dy[z]; if(min(nx, ny) >= 0 && nx < n && ny < m){ if(id[nx][ny] == 0){ if(A[nx][ny] == A[x][y]){ id[nx][ny] = id[x][y]; q.push(mp(nx, ny)); } }else if(id[nx][ny] != id[x][y]){ licznik[id[nx][ny]] = 1; toAdd.pb(id[nx][ny]); } } } } } void calc(){ id.assign(n, vi(m, 0)); k = 1; for(int i = 0; i < MAXM; i++){ liczSpec[i] = 0; idSpec[i] = 0; } for(auto ele : special){ liczSpec[ele] = 1; } int curr = 0; for(int i = 0; i < MAXM; i++){ if(liczSpec[i]){ idSpec[i] = curr++; } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(id[i][j] == 0){ id[i][j] = k; Rep[k] = k; pos[k].clear(); col[k] = A[i][j]; toAdd.clear(); for(int x = 0; x < sz(special); x++){ rep[k][x] = k; g[k][x].clear(); } bfs(i, j); for(auto ele : toAdd){ if(licznik[ele]){ licznik[ele] = 0; if(liczSpec[col[ele]]){ g[id[i][j]][idSpec[col[ele]]].pb(ele); } if(liczSpec[col[ele]]){ g[ele][idSpec[col[id[i][j]]]].pb(id[i][j]); } } } k++; } } } k--; } void updGrid(){ for(int i = 1; i <= k; i++){ for(auto ele : pos[i]){ A[ele.fi][ele.se] = col[i]; } } } void mergeGraph(int a, int b, int kol){ int repA = Find(a, kol); int repB = Find(b, kol); if(sz(g[repA][kol]) < sz(g[repB][kol])){ swap(repA, repB); } rep[repB][kol] = repA; for(auto ele : g[repB][kol]){ g[repA][kol].pb(ele); } g[repB][kol].clear(); } void merge(int a, int b){ if(sz(pos[a]) < sz(pos[b])){ swap(a, b); } for(auto ele : pos[b]){ id[ele.fi][ele.se] = a; pos[a].pb(ele); } pos[b].clear(); Rep[b] = a; for(int j = 0; j < sz(special); j++){ mergeGraph(a, b, j); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; A.resize(n, vi(m)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> A[i][j]; } } calc(); int q; cin >> q; for(int j = 0; j < q; j += B){ vector<pair<pii, int>> vec = {}; for(int i = j; i < min(q, j + B); i++){ int a, b, c; cin >> a >> b >> c; a--; b--; vec.pb(mp(mp(a, b), c)); } special.clear(); for(auto ele : vec){ special.pb(ele.se); } calc(); for(auto ele : vec){ int x = ele.fi.fi; int y = ele.fi.se; int c = ele.se; col[id[x][y]] = c; vi merging = g[Find(id[x][y], idSpec[c])][idSpec[c]]; for(auto u : merging){ if(col[Find2(u)] != c){ continue; } merge(u, id[x][y]); } } updGrid(); } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cout << A[i][j] << ' '; } cout << '\n'; } return 0; }