COI '19 #1 Paint

Points: 40 (partial)

Time limit: 3.0s

Memory limit: 512M

Problem type

We will represent the drawing area of MS Paint as a rectangular grid of unit squares divided into $R$ $R$ rows and $S$ $S$ columns. Each square of the grid represents a single pixel that can be colored in one of the $10^5$ $10^{5}$ different colors. When the user applies the so called bucket tool with color $A$ $A$ on a pixel $(r, s)$ $(r, s)$ which is colored in the color $B$ $B$ , then all pixels in the monochrome neighborhood of pixel $(r, s)$ $(r, s)$ change their color to $A$ $A$ . Monochrome neighborhood of a pixel $(r, s)$ $(r, s)$ is a set of pixels that are reachable by walking from $(r, s)$ $(r, s)$ in the four general directions (up, down, left and right) without changing the color of the pixel along the way. Note that the pixel $(r, s)$ $(r, s)$ is itself a part of its monochrome neighborhood.

You are given a starting image drawn in MS Paint along with $Q$ $Q$ instructions that should be executed in the given order. Each instruction tells you on which pixel should you apply the bucket tool and with what color. Your task is to how the image looks like after all instructions are executed.

Input Specification

The first line contains integers $R$ $R$ and $S$ $S$ from the task description. Each of the next $R$ $R$ lines contains $S$ $S$ non-negative integers less than $100\,000$ $100 000$ that represent the starting image drawn in MS Paint. More precisely, the $j$ $j$ -th number in the $i$ $i$ -th row of the image represents the color of the pixel $(i, j)$ $(i, j)$ . The next line contains an integer $Q$ $Q$ from the task description.

The $i$ $i$ -th of the next $Q$ $Q$ lines contains integers $r_i$ $r_{i}$ , $s_i$ $s_{i}$ , and $c_i$ $c_{i}$ $(1 \le r_i \le R, 1 \le s_i \le S, 0 \le c_i < 100\,000)$ $(1 \leq r_{i} \leq R, 1 \leq s_{i} \leq S, 0 \leq c_{i} < 100 000)$ , which represent the $i$ $i$ -th instruction that tells you to use the bucket tool with color $c_i$ $c_{i}$ on the pixel $(r_i, s_i)$ $(r_{i}, s_{i})$ .

Output Specification

You should output the final state of the image in the same format as it was given in the input.

Constraints

Subtask	Points	Constraints
1	8	$1 \le R \cdot S \le 10\,000, 1 \le Q \le 10\,000$ $1 \leq R \cdot S \leq 10 000, 1 \leq Q \leq 10 000$
2	9	$R = 1, 1 \le S \le 200\,000, 1 \le Q \le 100\,000$ $R = 1, 1 \leq S \leq 200 000, 1 \leq Q \leq 100 000$
3	31	$1 \le R \cdot S \le 200\,000, 1 \le Q \le 100\,000$ $1 \leq R \cdot S \leq 200 000, 1 \leq Q \leq 100 000$ Each pixel will in every moment be colored either in color $0$ $0$ or color $1$ $1$ .
4	52	$1 \le R \cdot S \le 200\,000, 1 \le Q \le 100\,000$ $1 \leq R \cdot S \leq 200 000, 1 \leq Q \leq 100 000$

Sample Input 1

Copy

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

Sample Output 1

Copy

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

Explanation for Sample Output 1

The figure from the task description corresponds to the input of the first example. White color corresponds to number $0$ $0$ , red color corresponds to number $1$ $1$ , blue color corresponds to number $2$ $2$ , green color corresponds to number $3$ $3$ and yellow color corresponds to number $4$ $4$ .

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

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

Sample Output 3

Copy

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

Comments

There are no comments at the moment.