시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 21 1 1 14.286%

문제

We will represent the drawing area of MS Paint as a rectangular grid of unit squares divided into R rows and S columns. Each square of the grid represents a single pixel that can be colored in one of the 105 different colors. When the user applies the so called bucket tool with color A on a pixel (r, s) which is colored in the color B, then all pixels in the monochrome neighborhood of pixel (r, s) change their color to A. Monochrome neighborhood of a pixel (r, s) is a set of pixels that are reachable by walking from (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) is itself a part of its monochrome neighborhood.

You are given a starting image drawn in MS Paint along with 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.

입력

The first line contains integers R and S from the task description.

Each of the next R lines contains S non-negative integers less than 100 000 that represent the starting image drawn in MS Paint. More precisely, the j-th number in the i-th row of the image represents the color of the pixel (i, j).

The next line contains an integer Q from the task description. The i-th of the next Q lines contains integers ri, si and ci (1 ≤ ri ≤ R, 1 ≤ si ≤ S, 0 ≤ ci < 100 000), which represent the i-th instruction that tells you to use the bucket tool with color ci on the pixel (ri, si).

출력

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

서브태스크

번호 배점 조건
1 8

1 ≤ R · S ≤ 10 000, 1 ≤ Q ≤ 10 000

2 9

R = 1, 1 ≤ S ≤ 200 000, 1 ≤ Q ≤ 100 000

3 31

1 ≤ R · S ≤ 200 000, 1 ≤ Q ≤ 100 000

Each pixel will in every moment be colored either in color 0 or color 1.

4 52

1 ≤ R · S ≤ 200 000, 1 ≤ Q ≤ 100 000

예제 입력 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

예제 출력 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

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

예제 입력 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

예제 출력 2

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

예제 입력 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

예제 출력 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

채점 및 기타 정보

  • 예제는 채점하지 않는다.