Description

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.

Input Format

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 Format

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

12 11
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 0 1 1 1
1 1 0 0 0 0 0 0 0 1 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 2 0 0 0 1 1
0 1 1 0 0 2 0 0 1 1 0
0 0 1 1 0 0 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0
2
5 5 3
6 2 4

1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 4 4 1 1 1 1
1 1 1 4 4 4 4 4 1 1 1
1 1 4 4 4 4 4 4 4 1 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 3 3 3 4 4 4 1
1 4 4 4 4 4 4 4 4 4 1
1 1 4 4 4 2 4 4 4 1 1
0 1 1 4 4 2 4 4 1 1 0
0 0 1 1 4 4 4 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0

4 4
1 0 1 3
1 3 2 2
3 3 1 2
2 2 1 3
3
1 2 3
3 2 1
4 2 3

1 1 1 3
1 1 2 2
1 1 1 2
3 3 1 3

6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 3 2 2 2 1
4
6 2 2
3 5 2
3 2 3
1 2 3

1 3 1 2 2 2
3 1 3 1 3 1
3 3 3 3 3 3
3 3 1 3 3 3
3 3 3 3 3 3
3 3 3 3 3 1

Hint

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。

Translated by ChatGPT 5