#include <vector>
#include <string>
#include <iostream>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <math.h>
#include <deque>
#include <algorithm>
#define ll long long
#define pii pair<int, int>
#define pip pair<int, pii>
using namespace std;
ll mod = 1000000007;
ll inf = 1LL << 50;
const int C = 100000;
vector<int> tree;
vector<int> ranks;
int boundCheck(int r, int c, int R, int S)
{
return r < R && r >= 0 && c < S && c >= 0;
}
void dfs(int r, int c, const vector<int> &grid, int R, int S, vector<unordered_set<int>> &edgeSet)
{
int index = r * S + c;
int comp = tree[index];
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};
for (int i = 0; i < 4; i++)
{
int nr = dr[i] + r;
int nc = dc[i] + c;
int nIndex = nr * S + nc;
if (boundCheck(nr, nc, R, S))
{
if (grid[nIndex] == grid[index] && tree[nIndex] == -1)
{
tree[nIndex] = comp;
dfs(nr, nc, grid, R, S, edgeSet);
}
else if (tree[nIndex] != -1 && tree[nIndex] != comp)
{
int nComp = tree[nIndex];
edgeSet[comp].insert(nComp);
edgeSet[nComp].insert(comp);
}
}
}
}
// finds root of tree with x in it (with memoization)
int find(int x)
{
return x == tree[x] ? x : tree[x] = find(tree[x]);
}
// links two components together
void link(int x, int y)
{
if (ranks[x] > ranks[y])
{
tree[y] = x;
}
else
{
tree[x] = y;
if (ranks[x] == ranks[y])
{
ranks[y]++;
}
}
}
void intoHeavy(int heavyComp, int comp, vector<int> &grid, vector<unordered_set<int>> &edgeList, vector<vector<vector<int>>> &neighborColors, vector<int> &heavyComps, vector<bool> &heavyCompMap)
{
// tree[comp] = heavyComp;
link(comp, heavyComp);
int parentComp = find(comp);
// cout << parentComp << " merge " << heavyComp << " " << comp << '\n';
for (int neighbor : edgeList[comp])
{
int ncomp = find(neighbor);
if (ncomp == parentComp)
{
continue;
}
edgeList[heavyComp].insert(ncomp);
neighborColors[heavyComp][grid[ncomp]].push_back(ncomp);
edgeList[ncomp].insert(parentComp);
}
if (parentComp == comp)
{
swap(edgeList[comp], edgeList[heavyComp]);
swap(neighborColors[comp], neighborColors[heavyComp]);
heavyCompMap[comp] = true;
heavyComps.push_back(comp);
}
}
void initNeighborColors(int heavyComp, vector<unordered_set<int>> &edgeList, vector<vector<vector<int>>> &neighborColors, vector<bool> &heavyCompMap, vector<int> &grid)
{
neighborColors[heavyComp].resize(C);
for (int neighborComp : edgeList[heavyComp])
{
// cout << "neighbor " << neighborComp << '\n';
neighborComp = find(neighborComp);
// if (!heavyCompMap[neighborComp])
// {
neighborColors[heavyComp][grid[neighborComp]].push_back(neighborComp);
//}
}
}
void lightlight(int destComp, int comp, vector<int> &grid, vector<bool> &heavyCompMap, vector<int> &heavyComps, vector<unordered_set<int>> &edgeList, vector<vector<vector<int>>> &neighborColors, int threshold)
{
if (edgeList[destComp].size() < edgeList[comp].size())
{
swap(comp, destComp);
}
link(comp, destComp);
// tree[comp] = destComp;
int parentComp = find(comp);
for (int neighbor : edgeList[comp])
{
int ncomp = find(neighbor);
if (ncomp == parentComp || edgeList[destComp].count(ncomp))
{
continue;
}
edgeList[destComp].insert(ncomp);
}
if (parentComp == comp)
{
swap(edgeList[comp], edgeList[destComp]);
swap(destComp, comp);
}
if (edgeList[destComp].size() >= threshold)
{
for (int neighbor : edgeList[destComp])
{
int ncomp = find(neighbor);
edgeList[ncomp].insert(destComp);
}
heavyCompMap[destComp] = true;
heavyComps.push_back(destComp);
initNeighborColors(destComp, edgeList, neighborColors, heavyCompMap, grid);
}
}
void merge(int comp, int preComp, vector<int> &grid, vector<bool> &heavyCompMap, vector<int> &heavyComps, vector<unordered_set<int>> &edgeList,
vector<vector<vector<int>>> &neighborColors, int threshold)
{
if (comp == preComp)
{
return;
}
if (heavyCompMap[comp])
{
if (heavyCompMap[preComp])
{
if (edgeList[comp].size() < edgeList[preComp].size())
{
swap(comp, preComp);
}
intoHeavy(comp, preComp, grid, edgeList, neighborColors, heavyComps, heavyCompMap);
}
else
{
intoHeavy(comp, preComp, grid, edgeList, neighborColors, heavyComps, heavyCompMap);
}
}
else
{
if (heavyCompMap[preComp])
{
intoHeavy(preComp, comp, grid, edgeList, neighborColors, heavyComps, heavyCompMap);
}
else
{
lightlight(preComp, comp, grid, heavyCompMap, heavyComps, edgeList, neighborColors, threshold);
}
}
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin.exceptions(cin.failbit);
int R, S;
cin >> R >> S;
int threshold = sqrt(R * S);
tree = vector<int>(R * S, -1);
ranks = vector<int>(R * S, 0);
vector<vector<vector<int>>> neighborColors(R * S);
vector<bool> heavyCompMap(R * S, false);
vector<int> heavyComps;
vector<unordered_set<int>> edgeList(R * S);
vector<int> grid(R * S);
for (int r = 0; r < R; r++)
{
for (int c = 0; c < S; c++)
{
int color;
cin >> color;
grid[r * S + c] = color;
}
}
vector<int> compList;
for (int r = 0; r < R; r++)
{
for (int c = 0; c < S; c++)
{
int index = r * S + c;
if (tree[index] == -1)
{
tree[index] = index;
dfs(r, c, grid, R, S, edgeList);
compList.push_back(index);
}
}
}
// for (auto comp : compList)
// {
// cout << comp << ": ";
// for (auto edge : edgeList[comp])
// {
// cout << edge << ", ";
// }
// cout << "\n";
// }
for (int comp : compList)
{
if (edgeList[comp].size() >= threshold)
{
heavyCompMap[comp] = true;
heavyComps.push_back(comp);
neighborColors[comp].resize(C);
}
}
for (int comp : heavyComps)
{
neighborColors[comp].resize(C);
for (int neighborComp : edgeList[comp])
{
neighborComp = find(neighborComp);
neighborColors[comp][grid[neighborComp]].push_back(neighborComp);
}
}
int q;
cin >> q;
;
for (int i = 0; i < q; i++)
{
int r, c, color;
cin >> r >> c >> color;
r--;
c--;
int comp = find(r * S + c);
grid[comp] = color;
if (heavyCompMap[comp])
{
vector<int> toMerge = neighborColors[comp][color];
// vector<int> toMerge(edgeList[comp].begin(), edgeList[comp].end());
for (auto ncomp : toMerge)
{
// cout << comp << " " << ncomp << "\n";
ncomp = find(ncomp);
if (comp != ncomp && grid[ncomp] == color)
{
merge(comp, ncomp, grid, heavyCompMap, heavyComps, edgeList, neighborColors, threshold);
}
comp = find(comp);
}
// neighborColors[comp][color].clear();
}
else
{
vector<int> neighbors(edgeList[comp].begin(), edgeList[comp].end());
for (auto ncomp : neighbors)
{
ncomp = find(ncomp);
if (comp != ncomp && grid[ncomp] == color)
{
merge(comp, ncomp, grid, heavyCompMap, heavyComps, edgeList, neighborColors, threshold);
}
comp = find(comp);
}
}
for (auto heavyComp : heavyComps)
{
heavyComp = find(heavyComp);
if (heavyComp != comp && edgeList[comp].count(heavyComp))
{
neighborColors[heavyComp][color].push_back(comp);
}
}
}
for (int r = 0; r < R; r++)
{
for (int c = 0; c < S; c++)
{
cout << grid[find(r * S + c)] << " ";
}
cout << "\n";
}
}
