#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)); } }; struct Area{ int col, id, f; map<int, vi> g; vi bigG; vector<pii> pos; }; const int MAXN = 3e5 + 7; const int B = 500; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; vector<vi> Id; int rep[MAXN]; int vis[MAXN]; vector<vi> a; int licznik = 1; vector<Area> vec; int n, m, Q; int k = 0; int Find(int A){ if(rep[A] == A){ return A; } return rep[A] = Find(rep[A]); } void MakeBig(int id){ vec[id].f = 1; licznik++; for(auto& [x, y] : vec[id].pos){ 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 && vis[Id[nx][ny]] != licznik && Id[nx][ny] != id){ vis[Id[nx][ny]] = licznik; vec[Id[nx][ny]].bigG.pb(id); vec[id].g[vec[Id[nx][ny]].col].pb(Id[nx][ny]); } } } } void bfs(int x, int y, int c){ Area xdd; vec.pb(xdd); Id[x][y] = c; vec[c].id = c; vec[c].col = a[x][y]; rep[c] = c; queue<pii> q; q.push(mp(x, y)); while(sz(q)){ auto [X, Y] = q.front(); q.pop(); vec[c].pos.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 && Id[nx][ny] == -1 && a[nx][ny] == a[x][y]){ Id[nx][ny] = c; q.push(mp(nx, ny)); } } } } void calc(){ Id.assign(n, vi(m, -1)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(Id[i][j] == -1){ bfs(i, j, k); k++; } } } k--; for(int i = 0; i < sz(vec); i++){ if(sz(vec[i].pos) >= B){ MakeBig(i); } } } void correctLarges(int id){ licznik++; vi nowe = {}; for(auto e : vec[id].bigG){ e = Find(e); if(e == id || !vec[e].f || vis[e] == licznik){ continue; } vis[e] = licznik; nowe.pb(e); } vec[id].bigG = nowe; nowe.clear(); } //merge zwraca id połączonego rejonu int merge(int id1, int id2){ if(sz(vec[id1].pos) < sz(vec[id2].pos)){ swap(id1, id2); } if(vec[id1].f != vec[id2].f){ if(!vec[id1].f){ MakeBig(id1); }else{ MakeBig(id2); } } rep[id2] = id1; for(auto ele : vec[id2].pos){ vec[id1].pos.pb(ele); Id[ele.fi][ele.se] = id1; } vector<pii>().swap(vec[id2].pos); if(sz(vec[id1].bigG) < sz(vec[id2].bigG)){ vec[id1].bigG.swap(vec[id2].bigG); } for(auto ele : vec[id2].bigG){ vec[id1].bigG.pb(ele); } vi().swap(vec[id2].bigG); correctLarges(id1); if(sz(vec[id1].g) < sz(vec[id2].g)){ vec[id1].g.swap(vec[id2].g); } for(auto& ele : vec[id2].g){ auto& lSmall = ele.se; auto& lBig = vec[id1].g[ele.fi]; if(sz(lBig) < sz(lSmall)){ lSmall.swap(lBig); } for(auto ele2 : lSmall){ lBig.pb(ele2); } vi().swap(lSmall); } if(!vec[id1].f && sz(vec[id1].pos) >= B){ MakeBig(id1); } return id1; } vi getGraph(int id, int ncol){ if(vec[id].f){ licznik++; vi ret = {}; for(auto& ele : vec[id].g[ncol]){ ele = Find(ele); if(ele != id && vec[ele].col == ncol && vis[ele] != licznik){ vis[ele] = licznik; ret.pb(ele); } } return ret; } licznik++; vi ret = {}; for(auto& [x, y] : vec[id].pos){ 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 && Id[nx][ny] != id && vis[Id[nx][ny]] != licznik && vec[Id[nx][ny]].col == ncol){ vis[Id[nx][ny]] = licznik; ret.pb(Id[nx][ny]); } } } return ret; } void upd(int id, int ncol){ vec[id].col = ncol; vi curr = getGraph(id, ncol); //cerr << id << ' ' << ncol << '\n'; //debug(curr); for(auto& ele : curr){ id = merge(id, ele); } for(auto ele : vec[id].bigG){ vec[ele].g[ncol].pb(id); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; a.assign(n, vi(m)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j]; } } calc(); // for(int i = 0; i < n; i++){ // for(int j = 0; j < m; j++){ // cerr << Id[i][j] << ' '; // } // cerr << '\n'; // } cin >> Q; for(int xd = 1; xd <= Q; xd++){ int x, y, nc; cin >> x >> y >> nc; x--; y--; upd(Id[x][y], nc); // for(int i = 0; i < n; i++){ // for(int j = 0; j < m; j++){ // cerr << vec[Id[i][j]].col << ' '; // } // cerr << '\n'; // } // cerr << "---\n"; // for(int i = 0; i < n; i++){ // for(int j = 0; j < m; j++){ // cerr << Id[i][j] << ' '; // } // cerr << '\n'; // } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cout << vec[Id[i][j]].col << ' '; } cout << '\n'; } return 0; }