#pragma GCC optimize ("O3") // #pragma GCC optimize ("O2") 以下で自動ベクトル化を行う場合は、#pragma GCC optimize ("tree-vectorize") も合わせて記述してください。 #pragma GCC target ("avx") // ターゲットの変更 sse4, avx, avx2 など #pragma GCC optimize ("fast-math") #include using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< string > vs; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; const int MAXH = 200; const int MAXW = 200; int H, W; int A[ MAXH ][ MAXW ]; void init(){ cin >> H >> W; for( int i = 0; i < H; ++i ) for( int j = 0; j < W; ++j ) cin >> A[ i ][ j ]; } const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; int cc_col[ MAXH * MAXW ]; struct dsu{ vi fa; dsu( int sz ){ fa = vi( sz ); for( int i = 0; i < sz; ++i ){ fa[ i ] = i; } } int find( int x ){ return fa[ x ] == x ? x : find( fa[ x ] ); } int unite( int x, int y ){ int a = find( x ); int b = find( y ); if( a == b ) return 0; fa[ b ] = a; return 1; } } *ccid_uf; set< int > cc_graph[ MAXH * MAXW ]; void preprocess(){ ccid_uf = new dsu( H * W ); for( int i = 0; i < H; ++i ){ for( int j = 0; j < W; ++j ){ if( ccid_uf->find( i * W + j ) != i * W + j ) continue; queue< tuple< int, int > > que; que.emplace( i, j ); cc_col[ i * W + j ] = A[ i ][ j ]; while( not que.empty() ){ int x, y; tie( x, y ) = que.front(); que.pop(); for( int di = 0; di < 4; ++di ){ int nx = x + dx[ di ]; int ny = y + dy[ di ]; if( not ( 0 <= nx and nx < H and 0 <= ny and ny < W ) ) continue; if( A[ x ][ y ] != A[ nx ][ ny ] ) continue; if( ccid_uf->find( nx * W + ny ) == i * W + j ) continue; ccid_uf->unite( i * W + j, nx * W + ny ); que.emplace( nx, ny ); } } } } for( int i = 0; i < H; ++i ){ for( int j = 0; j < W; ++j ){ for( int di = 0; di < 4; ++di ){ int nx = i + dx[ di ]; int ny = j + dy[ di ]; if( not ( 0 <= nx and nx < H and 0 <= ny and ny < W ) ) continue; if( A[ i ][ j ] == A[ nx ][ ny ] ) continue; cc_graph[ ccid_uf->find( i * W + j ) ].emplace( ccid_uf->find( nx * W + ny ) ); } } } } void solve(){ int Q; cin >> Q; for( int i = 0; i < Q; ++i ){ int R, C, X; cin >> R >> C >> X; --R, --C; if( cc_col[ ccid_uf->find( R * W + C ) ] == X ) continue; cc_col[ ccid_uf->find( R * W + C ) ] = X; set< int > vis; for( int adj_cc : cc_graph[ ccid_uf->find( R * W + C ) ] ){ for( int adj_adj_cc : cc_graph[ adj_cc ] ){ if( adj_adj_cc == ccid_uf->find( R * W + C ) ) continue; if( vis.count( adj_adj_cc ) ) continue; cc_graph[ adj_adj_cc ].erase( adj_cc ); cc_graph[ adj_adj_cc ].emplace( ccid_uf->find( R * W + C ) ); vis.emplace( adj_adj_cc ); } ccid_uf->unite( R * W + C, adj_cc ); cc_graph[ adj_cc ].clear(); } for( int adj_adj_cc : vis ){ cc_graph[ ccid_uf->find( R * W + C ) ].emplace( adj_adj_cc ); } } for( int i = 0; i < H; ++i ){ for( int j = 0; j < W; ++j ){ // cout << ccid_uf->find( i * W + j ) << " \n"[ j + 1 == W ]; cout << cc_col[ ccid_uf->find( i * W + j ) ] << " \n"[ j + 1 == W ]; } } } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }