#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);
}
}
vec[id].g[ncol].clear();
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);
}
licznik++;
for(auto ele : vec[id].bigG){
ele = Find(ele);
if(vec[ele].f && ele != id && vis[ele] != licznik){
vis[ele] = licznik;
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 << " \n"[j + 1 == m];
}
}
return 0;
}
