Problem Description

You must be familiar with the fill tool in drawing software. When applied at the pixel level, if all pixels in a large connected block have the same color, coloring a single pixel will result in the entire connected block being colored.

Given a pixel grid of size $R \times S$ and $Q$ coloring operations:

• Color the pixel at $(r_i, s_i)$ with color $c_i$.

Determine the final state of the pixel grid after all coloring operations.

Input Format

The first line contains two integers $R$ and $S$ representing the size of the pixel grid.
The next $R$ lines each contain $S$ integers representing the initial colors of the pixel grid.
The $R+2$th line contains an integer $Q$ representing the number of operations.
The next $Q$ lines each contain three integers $r_i, s_i, c_i$ representing a coloring operation.

Output Format

Output $R$ lines, each containing $S$ integers representing the final state of the pixel grid.

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

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

Output Sample #2

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

Input Sample #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

Output Sample #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

Notes/Hints

Sample 1 Explanation

Assuming $0$ is white, $1$ is red, $2$ is blue, $3$ is green, $4$ is yellow, the following diagram illustrates the changes:

Data Size and Constraints

This problem uses batched testing.

• 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$, colors are only $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 data, $1 \le r_i \le R$, $1 \le s_i \le S$, $0 \le c_i \le 10^5$, the color range is $[0, 10^5]$.

Notes

Translated from the Croatian Olympiad in Informatics 2020 A Paint.

见题面 Input 部分

见题面 Output 部分