P8427 [COI 2020] Paint

You must have used the one-click fill tool in drawing software. If we look at it on the pixel level: if all pixels in a large connected component have the same color, then recoloring one pixel will recolor all pixels in that connected component. Now you are given an $R \times S$ pixel image and $Q$ recoloring operations: - Recolor $(r_i, s_i)$ to color $c_i$. Output the entire image after all recoloring operations.

The first line contains two integers $R, S$, representing the size of the pixel image. The next $R$ lines each contain $S$ integers, representing the initial colors of the image. Line $R + 2$ contains an integer $Q$, representing the number of operations. The next $Q$ lines each contain three integers $r_i, s_i, c_i$, representing one recoloring operation.

Output $R$ lines, each containing $S$ integers, representing the recolored pixel image.

#### Explanation for Sample 1 Assume $0$ is white, $1$ is red, $2$ is blue, $3$ is green, and $4$ is yellow, as shown in the figure below:  #### Constraints **This problem uses bundled testdata.** - Subtask 1 (8 pts): $1 \le R \times S \le 10^4$, $1 \le Q \le 10^4$. - Subtask 2 (9 pts): $R = 1$, $1 \le S \le 2 \times 10^5$, $1 \le Q \le 10^5$. - Subtask 3 (31 pts): $1 \le R \times S \le 2 \times 10^5$, $1 \le Q \le 10^5$, and there are only colors $0$ and $1$. - Subtask 4 (52 pts): $1 \le R \times S \le 2 \times 10^5$, $1 \le Q \le 10^5$. For $100\%$ of the testdata, $1 \le r_i \le R$, $1 \le s_i \le S$, $0 \le c_i \le 10^5$, and the color range is $[0, 10^5]$. #### Notes Translated from [Croatian Olympiad in Informatics 2020 A Paint](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。 Translated by ChatGPT 5