rt,mel4个点

#include <bits/stdc++.h>
//#define int long long  
using namespace std;
int  n,m,q,id,vis[200005],clo[200005],st,fa[200005],big[200005],tot[200005];
int  X[5]={0,1,-1,0,0},Y[5]={0,0,0,1,-1};
vector <int > a[200005];//
vector <int > lj[200005],p[200005];
unordered_map<int ,vector<int > >c[200005];
vector<int > tong;
 int  check(int  x,int  y){
	return (x<1||x>n||y<1||y>m);
}
 int  tt(int  x,int  y){
	return (x-1)*m+y;
}
 int  tx(int  o){
	return (o-1)/m+1;
}
 int  ty(int  o){
	return (o-1)%m+1;
}
 int  find(int  x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
 void dfs(int  x,int  y,int  cs,int  di){
	if(check(x,y)||vis[tt(x,y)]||a[x][y]!=cs){
		return ;
	} 
	p[di].push_back(tt(x,y));
	vis[tt(x,y)]=1;
	tot[tt(x,y)]=di;
	for(int i=1;i<=4;i++){
		dfs(x+X[i],y+Y[i],cs,di);
	}
}
 void makebig(int  i){
	big[i]=1;
	
	for(int j=0;j<p[i].size();j++){
		int  x=tx(p[i][j]),y=ty(p[i][j]);
		for(int ppp=1;ppp<=4;ppp++){
			int op=tot[tt(x+X[ppp],y+Y[ppp])];
			if(check(x+X[ppp],y+Y[ppp]))continue;
			if(!vis[op]&&op!=i){
				vis[op]=1;
				tong.push_back(op);
				lj[op].push_back(i);
				c[i][clo[op]].push_back(op);
			}
		}
	}
	for(int i=0;i<tong.size();i++){
		vis[tong[i]]=0;
	}
	tong.clear();
}
 int merge(int  x,int  y){
	if(big[x]&&!big[y])makebig(y);
	if(!big[x]&&big[y])makebig(x);
	
	fa[y]=x;
	for(int i=0;i<p[y].size();i++){
		p[x].push_back(p[y][i]);
		tot[p[y][i]]=x;
	}
	if(lj[x].size()<lj[y].size()){
		lj[x].swap(lj[y]);
	}
	for(int i=0;i<lj[x].size();i++){
		lj[y].push_back(lj[x][i]);
	}
//	vector<int>().swap(lj[x]);
	lj[x].clear();
	for(int i=0;i<lj[y].size();i++){
		if(!vis[lj[y][i]]&&find(lj[y][i])!=x){
			vis[lj[y][i]]=1;
			lj[x].push_back(lj[y][i]);
		}
	}
	for(int i=0;i<lj[x].size();i++){
		vis[lj[x][i]]=0;
	}
	if(c[y].size()>c[x].size())c[y].swap(c[x]);
	for(auto &[C,l] : c[y]){
		auto &L = c[x][C];
		if(l.size() > L.size()) l.swap(L);
		for(int zz : l) L.push_back(zz);
//		vector<int>().swap(l);
		l.clear(); 
	}
	
//	for(int i=0;i<c[x][clo[x]].size();i++){
//		c[y][clo[x]].push_back(c[x][clo[x]][i]);
//	}
//	c[x][clo[x]].clear();
//	for(int i=0;i<c[y][clo[x]].size();i++){
//		if(!vis[c[x][clo[y]][i]]&&c[x][clo[y]][i]!=x&&c[x][clo[y]][i]!=y){
//			vis[c[x][clo[y]][i]]=1;
//			c[x][clo[x]].push_back(c[x][clo[y]][i]);
//		}
//	}
//	for(int i=0;i<c[x][clo[x]].size();i++){
//		vis[c[x][clo[x]][i]]=0;
//	}
	c[y].clear();
	if(!big[x]&&p[x].size()>st){
		makebig(x);
	}
	return x;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


	cin>>n>>m;
	st=sqrt((n*m));
	int  xxxx;
	for(int i=1;i<=n;i++){
		a[i].push_back(0);
		for(int j=1;j<=m;j++){
			
			cin>>xxxx;
			a[i].push_back(xxxx);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!vis[tt(i,j)]){
				clo[++id]=a[i][j];
				dfs(i,j,a[i][j],id);
			}
		}
	}
	
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<clo[tot[tt(i,j)]]<<" ";
//		}
//		cout<<"\n";
//	}
	
	for(int i=1;i<=n*m;i++){
		vis[i]=0;
	}
	for(int i=1;i<=id;i++){
		fa[i]=i;
	}
	for(int i=1;i<=id;i++){
		if(p[i].size()>=st){
			makebig(i);
		}
	}
	
	cin>>q;
	while(q--){
		int  x,y,z;
		cin>>x>>y>>z;
		int  u=tot[tt(x,y)];
		clo[u]=z;
		vector<int >hb;
		if(big[u]){
			for(int i=0;i<c[u][z].size();i++){
				int  v=find(c[u][z][i]);
				if(!vis[v]&&v!=u&&clo[v]==z){
					hb.push_back(v);
					vis[v]=1;
				}
			}
//			vector<int>().swap(c[u][z]);
			c[u][z].clear();
		}else{
			int xx,yy,xxx,yyy;
			for(int i=0;i<p[u].size();i++){
				xx=tx(p[u][i]),yy=ty(p[u][i]);
				for(int j=1;j<=4;j++){
					xxx=xx+X[j],yyy=yy+Y[j];
					if(!check(xxx,yyy)){
						int  v=tot[tt(xxx,yyy)];
						if(clo[v]==z&&!vis[v]&&v!=u){
							hb.push_back(v);
							vis[v]=1;
						}
					}
				}
			}
		}
		for(int i=0;i<hb.size();i++){
			u=merge(u,hb[i]);
			vis[hb[i]]=0;
		}
//		vector<int>().swap(hb);
		hb.clear();
		for(int i=0;i<lj[u].size();i++){
			int  v=find(lj[u][i]);
			if(v!=u&&!vis[v]){
				vis[v]=1;
				hb.push_back(v);
				c[v][z].push_back(u);
			}
		}
		for(int i=0;i<hb.size();i++){
			vis[hb[i]]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<clo[tot[tt(i,j)]]<<" ";
		}
		cout<<"\n";
	}
}