import std.algorithm, std.conv, std.range, std.stdio, std.string; void main() { auto rd1 = readln.split.to!(size_t[]), h = rd1[0], w = rd1[1], hw = h * w; auto a = new int[](hw); foreach (i; 0..h) { auto rd2 = readln.split.to!(int[]); a[i*w..(i+1)*w][] = rd2[]; } auto uf = UnionFind!size_t(hw); foreach (i; 0..hw) { if (i % w != w-1 && a[i] == a[i+1]) uf.unite(i, i+1); if (i / w != h-1 && a[i] == a[i+w]) uf.unite(i, i+w); } auto nn = new size_t[][](hw); foreach (i; 0..hw) { if (i % w != 0 && a[i] != a[i-1]) nn[uf.find(i)] ~= uf.find(i-1); if (i / w != 0 && a[i] != a[i-w]) nn[uf.find(i)] ~= uf.find(i-w); if (i % w != w-1 && a[i] != a[i+1]) nn[uf.find(i)] ~= uf.find(i+1); if (i / w != h-1 && a[i] != a[i+w]) nn[uf.find(i)] ~= uf.find(i+w); } foreach (i; 0..hw) { nn[i].sort(); nn[i] = nn[i].uniq.array; } auto q = readln.chomp.to!size_t; foreach (_; 0..q) { auto rd3 = readln.split, r = rd3[0].to!size_t, c = rd3[1].to!size_t, x = rd3[2].to!int; auto i = uf.find((r-1) * w + (c-1)); a[i] = x; foreach (j; nn[i]) { if (a[j] == x) { uf.unite(i, j); nn[i] ~= nn[j]; } } } foreach (i; 0..h) { foreach (j; 0..w) { auto k = uf.find(i * w + j); write(a[k]); if (j < w-1) write(" "); } writeln(); } } struct UnionFind(T) { import std.algorithm, std.range; T[] p; // parent const T s; // sentinel const T n; this(T n) { this.n = n; p = new T[](n); s = n + 1; p[] = s; } T find(T i) { if (p[i] == s) { return i; } else { p[i] = find(p[i]); return p[i]; } } void unite(T i, T j) { auto pi = find(i), pj = find(j); if (pi != pj) p[pj] = pi; } bool isSame(T i, T j) { return find(i) == find(j); } auto groups() { auto g = new T[][](n); foreach (i; 0..n) g[find(i)] ~= i; return g.filter!(l => !l.empty); } }