import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.Scanner; import java.util.Set; public class Main { public static final int[][] nexts = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public static boolean is_in(int x, int y, int W, int H){ return 0 <= x && x < W && 0 <= y && y < H; } public static class UnionFind{ int[] par; // public UnionFind(int n){ par = new int[n]; for(int i = 0; i < n; i++){ par[i] = -1; } } public int find(int x){ if(par[x] < 0){ return x; }else{ return par[x] = find(par[x]); } } public boolean union(int x, int y){ x = find(x); y = find(y); if(x != y){ if(par[y] < par[x]) { // 多い方が根になるようにスワップする. int tmp = x; x = y; y = tmp; } par[x] += par[y]; par[y] = x; return true; }else{ return false; } } public boolean same(int x, int y){ return find(x) == find(y); } public int size(int x){ return -par[find(x)]; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); final int H = sc.nextInt(); final int W = sc.nextInt(); boolean[][] colors = new boolean[H][W]; for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ colors[i][j] = sc.nextInt() == 1; } } UnionFind uf = new UnionFind(H * W); ArrayList> adjs = new ArrayList>(H * W); for(int y = 0; y < H; y++){ for(int x = 0; x < W; x++){ final HashSet set = new HashSet(); final int id = y * W + x; final int uf_id = uf.find(id); for(int[] next : nexts){ final int nx = x + next[0]; final int ny = y + next[1]; if(!is_in(nx, ny, W, H)){ continue; }else if(colors[ny][nx] == colors[y][x]){ //uf.union(ny, nx); continue; } final int next_id = ny * W + nx; set.add(next_id); } adjs.add(set); } } for(int y = 0; y < H; y++){ for(int x = 0; x < W; x++){ final int id = y * W + x; final int uf_id = uf.find(id); for(int[] next : nexts){ final int nx = x + next[0]; final int ny = y + next[1]; if(!is_in(nx, ny, W, H)){ continue; } final int next_id = ny * W + nx; final int next_uf_id = uf.find(next_id); if(colors[next_uf_id / W][next_uf_id % W] == colors[uf_id / W][uf_id % W]){ HashSet merged = new HashSet(); for(final int uf_ids : adjs.get(uf_id)){ if(uf.find(uf_ids) != uf.find(next_uf_id)){ merged.add(uf.find(uf_ids)); } } for(final int next_uf_ids : adjs.get(next_uf_id)){ if(uf.find(next_uf_ids) != uf.find(uf_id)){ merged.add(uf.find(next_uf_ids)); } } uf.union(uf_id, next_uf_id); adjs.set(uf_id, merged); adjs.set(next_uf_id, merged); } } } } final int Q = sc.nextInt(); for(int i = 0; i < Q; i++){ final int y = sc.nextInt() - 1; final int x = sc.nextInt() - 1; final boolean color = sc.nextInt() == 1; final int id = y * W + x; final int uf_id = uf.find(id); if(colors[uf_id / W][uf_id % W] == color){ continue; } colors[uf_id / W][uf_id % W] = color; //System.out.println(i + " orig : " + (uf_id / W) + " " + (uf_id % W)); for(final int next_uf_id : adjs.get(uf_id)){ //System.out.println(i + " : " + (next_uf_id / W) + " " + (next_uf_id % W)); HashSet merged = new HashSet(); for(final int uf_ids : adjs.get(uf_id)){ if(uf.find(uf_ids) != uf.find(next_uf_id)){ merged.add(uf.find(uf_ids)); } } for(final int next_uf_ids : adjs.get(next_uf_id)){ if(uf.find(next_uf_ids) != uf.find(uf_id)){ merged.add(uf.find(next_uf_ids)); } } uf.union(uf_id, next_uf_id); adjs.set(uf_id, merged); adjs.set(next_uf_id, merged); } } for(int y = 0; y < H; y++){ for(int x = 0; x < W; x++){ final int uf_id = uf.find(y * W + x); if(x != 0){ System.out.printf(" "); } System.out.print(colors[uf_id / W][uf_id % W] ? 1 : 0); } System.out.println(); } } }