// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;
#define cell(x, y) (((x) - 1) * n + (y))
typedef long long ll;
typedef pair<int, int> ii;
const int MAX_N = 2e5;
const int MAX_Q = 1e5;
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
struct Query {
int x, y, color;
Query() {};
Query(int x, int y, int color) : x(x), y(y), color(color) {};
};
struct DSU {
vector<int> par, sz, lef, rig, color;
vector<set<int>> border;
int n;
int findSet(int u) {
return u == par[u] ? u : par[u] = findSet(par[u]);
};
int getColor(int u) {
return color[findSet(u)];
};
void setColor(int u, int c) {
color[findSet(u)] = c;
};
bool unionSet(int u, int v, int c) {
u = findSet(u), v = findSet(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
if (border[u].size() < border[v].size()) border[u].swap(border[v]);
for (int node : border[v])
if (findSet(node) != u) border[u].insert(node);
setColor(u, c);
sz[u] += sz[v];
par[v] = u;
lef[u] = min(lef[u], lef[v]);
rig[u] = max(rig[u], rig[v]);
return true;
};
DSU() {};
DSU(int n) : n(n) {
par.resize(n + 1), color.resize(n + 1);
lef.resize(n + 1), rig.resize(n + 1);
border.resize(n + 1), sz.resize(n + 1);
for (int u = 1; u <= n; u++) {
par[u] = u;
lef[u] = u, rig[u] = u;
sz[u] = 1;
};
};
};
int m, n, q;
vector<Query> queries;
vector<vector<int>> a;
bool valid(int x, int y) {
return (x >= 1 && x <= m && y >= 1 && y <= n);
};
namespace SUBTASK_1 {
const int MN = 1e4;
bool vis[MN + 5];
vector<vector<int>> b;
bool checkSubtask() {
return m * n <= 1e4 && q <= 1e4;
};
void dfs(int x, int y, int color) {
vis[cell(x, y)] = true;
for (int i = 0; i < 4; i++) {
int u = x + dx[i];
int v = y + dy[i];
if (valid(u, v) && !vis[cell(u, v)] && b[u][v] == b[x][y]) dfs(u, v, color);
};
b[x][y] = color;
};
void Solve() {
b = a;
for (const Query &q : queries) {
int x = q.x, y = q.y, color = q.color;
for (int i = 1; i <= m * n; i++) vis[i] = false;
dfs(x, y, color);
};
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cout << b[i][j] << " ";
};
cout << '\n';
};
};
}; // namespace SUBTASK_1
namespace SUBTASK_2 {
const int M = 1;
const int N = MAX_N;
const int Q = MAX_Q;
bool checkSubtask() {
return m <= M && n <= N && q <= Q;
};
void Solve() {
DSU DSU(n);
for (int i = 1; i <= n; i++) {
DSU.setColor(i, a[1][i]);
};
for (int i = 1; i < n; i++) {
if (a[1][i] == a[1][i + 1]) {
DSU.unionSet(i, i + 1, a[1][i]);
};
};
for (const Query &q : queries) {
int idx = q.y, color = q.color;
if (color == DSU.getColor(idx)) continue;
DSU.setColor(idx, color);
int root = DSU.findSet(idx);
int l = DSU.lef[root], r = DSU.rig[root];
int newL = (l - 1 == 0 ? idx : DSU.findSet(l - 1));
int newR = (r + 1 > n ? idx : DSU.findSet(r + 1));
if (DSU.color[newL] == color) {
DSU.unionSet(newL, idx, color);
};
if (DSU.color[newR] == color) {
DSU.unionSet(newR, idx, color);
};
};
for (int i = 1; i <= n; i++) cout << DSU.getColor(i) << ' ';
cout << '\n';
};
}; // namespace SUBTASK_2
void printMatrix(int m, int n, const vector<vector<int>> &a) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << ' ';
};
cout << '\n';
};
};
namespace SUBTASK_3 {
const int SIZE = 2e5;
bool checkSubtask() {
for (Query &q : queries)
if (q.color > 1) return false;
return true;
};
vector<vector<int>> rotate(int m, int n, const vector<vector<int>> &a) {
vector<vector<int>> b(n + 2, vector<int>(m + 2, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[i][j] = a[j][i];
};
};
return b;
};
void Solve() {
DSU DSU(m * n);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int u = cell(i, j);
DSU.setColor(u, a[i][j]);
for (int k = 0; k < 4; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (valid(x, y)) {
int v = cell(x, y);
if (a[x][y] != a[i][j])
DSU.border[u].insert(v);
else
DSU.unionSet(u, v, a[x][y]);
};
};
};
};
for (const Query &q : queries) {
int x = q.x, y = q.y, color = q.color;
int u = cell(x, y);
if (color == DSU.getColor(u)) continue;
int root = DSU.findSet(u);
DSU.setColor(root, color);
bool merged_in_pass = true;
while (merged_in_pass) {
merged_in_pass = false;
set<int> current_border = DSU.border[root];
set<int> visited_neighbor_roots;
for (int v_cell : current_border) {
int v_root = DSU.findSet(v_cell);
if (v_root == root || visited_neighbor_roots.count(v_root)) {
continue;
};
visited_neighbor_roots.insert(v_root);
if (DSU.getColor(v_root) == color) {
DSU.unionSet(root, v_root, color);
root = DSU.findSet(root);
merged_in_pass = true;
};
};
};
};
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] = DSU.getColor(cell(i, j));
};
};
printMatrix(m, n, a);
};
}; // namespace SUBTASK_3
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen("PAINT.INP", "r")) {
freopen("PAINT.INP", "r", stdin);
freopen("PAINT.OUT", "w", stdout);
};
cin >> m >> n;
a.resize(m + 2, vector<int>(n + 2, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
};
};
cin >> q;
queries.resize(q);
for (Query &q : queries) cin >> q.x >> q.y >> q.color;
if (SUBTASK_1::checkSubtask())
return SUBTASK_1::Solve(), 0;
if (SUBTASK_2::checkSubtask())
return SUBTASK_2::Solve(), 0;
SUBTASK_3::Solve();
};
