T3 良（$\text{liang}$）

题目描述

mspaint 的一个功能是一键填充。

具体的，对于一个像素矩阵来说，对一个像素染色，会将与其颜色相同的四连通连通块染色。

现在给定一个 $N\times M$ 的像素图，有 $Q$ 次染色操作，每次把 $(r_i,c_i)$ 染为颜色 $w_i$。

求出 $Q$ 次操作后的像素图。

输入格式

第一行两个整数 $N,M$ 代表像素图大小。

接下来 $N$ 行每行 $M$ 个整数，代表像素图的初始颜色。

接下来一行一个整数 $Q$ 代表操作个数。

接下来 $Q$ 行每行三个整数 $r_i,c_i,w_i$ 代表一次染色操作。

输出格式

$N$ 行 $M$ 列代表最终的像素图。

数据范围

Subtask 1（8 pts）：$1 \le N \times M \le 10^4$，$1 \le Q \le 10^4$。

Subtask 2（9 pts）：$N=1$，$1 \le M\le 2 \times 10^5$，$1 \le Q \le 10^5$。

Subtask 3（31 pts）：$1 \le N \times M \le 2 \times 10^5$，$1 \le Q \le 10^5$，颜色只有 $0$ 和 $1$。

Subtask 4（52 pts）：$1 \le N \times M \le 2 \times 10^5$，$1 \le Q \le 10^5$。

对于 $100\%$ 的数据，$1 \le r_i \le R$，$1 \le c_i \le M$，$0 \le w_i \le 10^5$，颜色区间为 $[0,10^5]$。