페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8228
서브태스크

마스킹 테이프 1초 1024MB

문제

정올이는 종이와 마스킹 테이프를 사용하여 색칠을 하며 놀고 있다.

종이는 직사각형 모양으로, 세로 H 행, 가로 W 열의 칸이 그려져 있다. 위에서 i 번째 행 (1 ≦ i ≦ H), 왼쪽에서 j 번째 열 (1 ≦ j ≦ W)의 칸을 칸 (i, j)라고 부른다.

각각의 칸에는 색이 하나 정해져 있으며, 색은 정수로 표현되고 처음에는 모든 칸의 색은 0이다.

정올이는 이 종이와 마스킹 테이프를 사용하여 Q 번의 작업을 한다. k 번째 (1 ≦ k ≦ Q) 작업은 정수 q_k 값에 따라 다음과 같이 설명된다.

q_k = 1일 경우, 이 작업은 정수 x_k, y_k, c_k로 표현된다. 칸 (x_k, y_k), (x_k + 1, y_k), (x_k, y_k + 1), (x_k + 1, y_k + 1)에 대해, 그 칸이 마스킹 테이프로 덮여 있지 않으면 그 칸의 색을 c_k로 변경한다. 마스킹 테이프로 덮여 있으면 그 칸은 아무것도 하지 않는다.
q_k = 2일 경우, 이 작업은 정수 x_k, y_k로 표현된다. 칸 (x_k, y_k), (x_k + 1, y_k), (x_k, y_k + 1), (x_k + 1, y_k + 1)에 마스킹 테이프를 덮는다.
Q번의 작업이 끝난 후, 모든 마스킹 테이프를 벗긴다. 이때, 어떤 칸의 마스킹 테이프를 벗겼을 때 그 칸의 색은 마스킹 테이프로 덮기 직전의 색과 같다.

Q번의 작업 정보가 주어졌을 때, 최종적으로 종이의 모든 칸의 색을 구하는 프로그램을 작성하시오.


입력

첫 줄에 세 정수 H,W,Q가 주어진다.

다음 Q줄에 걸쳐 쿼리가 주어진다. 각 쿼리는 q_k, x_k, y_k, c_k 혹은 q_k, x_k, y_k의 형식으로 주어진다.

[제약 조건]

  • 2 \le H,W \le 500

  • 1\le Q\le 200,000

  • q_k는 1 또는 2 중 하나로 주어진다 (1 ≦ k ≦ Q).

  • q_k = 1일 경우, 1 ≦ x_k ≦ H - 1,\ 1 ≦ y_k ≦ W - 1,\ 1 ≦ c_k ≦ 10^9 (1 ≦ k ≦ Q).

  • q_k = 2일 경우, 1 ≦ xk ≦ H - 1,\ 1 ≦ yk ≦ W - 1 (1 ≦ k ≦ Q).

  • 입력되는 값은 모두 정수이다.


출력

최종적으로 종이의 모든 칸의 색을 H행으로 출력하시오.

i행 (1 ≦ i ≦ H)에는 W개의 정수를 공백으로 구분하여 출력하시오.

여기서 j번째 (1 ≦ j ≦ W)에 출력할 정수는 칸 (i, j)의 색이다.


부분문제

번호 점수 조건
#132점

H = 2，W = 2，q_k = 1 (1 ≦ k ≦ Q)．

#232점

q_k = 1 (1 ≦ k ≦ Q)．

#336점

추가 제약 조건 없음


예제1

입력
5 5 4
1 2 2 1
2 1 2
2 3 3
1 1 3 5
출력
0 0 0 5 0
0 1 1 5 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

1번 작업 (q1 = 1)

  • (2, 2), (2, 3), (3, 2), (3, 3) 칸의 색을 1로 변경합니다.

  • 이 작업 후, 종이의 상태는 다음과 같습니다:

0 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

2번 작업 (q2 = 2)

  • (1, 2), (1, 3), (2, 2), (2, 3) 칸을 마스킹 테이프를 덮습니다.

  • 이 작업 후, 종이의 상태는 다음과 같습니다:

0 0* 0* 0 0
0 1* 1* 0 0
0 1  1  0 0
0 0  0  0 0
0 0  0  0 0

3번 작업 (q3 = 2)

  • (3, 3), (3, 4), (4, 3), (4, 4) 칸을 마스킹 테이프를 덮습니다.

  • 이 작업 후, 종이의 상태는 다음과 같습니다:

0 0* 0* 0  0 
0 1* 1* 0  0 
0 1  1* 0* 0 
0 0  0* 0* 0 
0 0  0  0  0

4번 작업 (q4 = 1)

  • (1, 4), (2, 4) 칸의 색을 5로 변경합니다. (마스킹 테이프에 덮이지 않은 칸에 대해서만 색을 변경합니다)

  • (1, 3), (2, 3)은 이미 마스킹 테이프에 덮여 있으므로 아무런 변화가 없습니다.

  • 이 작업 후, 종이의 상태는 다음과 같습니다:

0 0* 0* 5  0
0 1* 1* 5  0
0 1  1* 0* 0 
0 0  0* 0* 0 
0 0  0  0  0

최종 결과

최종적으로 종이의 모든 칸의 색을 구하면 다음과 같습니다:

0 0 0 5 0 
0 1 1 5 0 
0 1 1 0 0 
0 0 0 0 0 
0 0 0 0 0

이러한 방식으로 각 작업을 처리하고 결과를 출력할 수 있습니다.


예제2

입력
5 5 3
1 1 1 2
1 3 3 3
1 2 4 2
출력
2 2 0 0 0
2 2 0 2 2
0 0 3 2 2
0 0 3 3 0
0 0 0 0 0

예제3

입력
10 10 10
2 5 7
2 5 6
1 5 6 1
1 9 2 1
2 1 1
1 2 4 2
2 3 2
1 2 2 3
1 9 9 2
1 8 8 1
출력
0 0 0 0 0 0 0 0 0 0
0 0 3 2 2 0 0 0 0 0
0 0 0 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 1 1 2
0 1 1 0 0 0 0 0 2 2

태그

출처

JOI 2025 예선2

역링크 공식 문제집만