페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

입력
554
1221
212
233
1135
출력
00050
01150
01100
00000
00000

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

입력
553
1112
1333
1242
출력
22000
22022
00322
00330
00000

예제3

입력
101010
257
256
1561
1921
211
1242
232
1223
1992
1881
출력
0000000000
0032200000
0002200000
0000000000
0000000000
0000000000
0000000000
0000000110
0110000112
0110000022

태그

출처

JOI 2025 예선2

역링크