hanzch   1년 전

마스킹 테이프 (Masking Tape) 서브태스크 다국어

시간 제한 메모리 제한
2 초 2048 MB

문제

JOI 군은 종이와 마스킹 테이프를 사용하여 색칠하며 놀고 있습니다.

종이는 직사각형이며, 세로 H행, 가로 W열의 격자가 그려져 있습니다. 위에서부터 i행째 (1 ≦ i ≦ H), 왼쪽에서부터 j열째 (1 ≦ j ≦ W)의 칸을 칸 (i, j)라고 부릅니다.

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

JOI 군은 이 종이와 마스킹 테이프를 이용하여 Q번의 작업을 수행합니다. k번째 (1 ≦ k ≦ Q) 작업은 정수 qk의 값에 따라 다음과 같이 설명됩니다.

  • qk = 1인 경우, 이 작업은 정수 xk, yk, ck로 표현됩니다. 칸 (xk, yk), (xk + 1, yk), (xk, yk + 1), (xk + 1, yk + 1) 각각에 대해, 칸이 마스킹 테이프로 덮여있지 않다면, 그 칸의 색을 ck로 변경합니다. 칸이 마스킹 테이프로 덮여있다면, 그 칸에는 아무것도 하지 않습니다.
  • qk = 2인 경우, 이 작업은 정수 xk, yk로 표현됩니다. 칸 (xk, yk), (xk + 1, yk), (xk, yk + 1), (xk + 1, yk + 1)을 마스킹 테이프로 덮습니다.

Q번의 작업이 끝난 후, 모든 마스킹 테이프를 제거합니다. 특정 칸의 마스킹 테이프를 제거했을 때, 그 칸의 색은 마스킹 테이프로 덮이기 직전의 색과 동일하게 됩니다.

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

입력

입력은 다음 형식으로 주어집니다.

H W Q
(Query 1)
(Query 2)
:
(Query Q)

각 (Query k) (1 ≦ k ≦ Q)에는 몇 개의 정수가 공백으로 구분되어 적혀 있습니다. 그 중 첫 번째 정수가 qk이며, 이 행의 내용은 다음 중 하나입니다.

  • qk = 1인 경우, 이 행에는 이어서 3개의 정수 xk, yk, ck가 공백으로 구분되어 적혀 있습니다.
  • qk = 2인 경우, 이 행에는 이어서 2개의 정수 xk, yk가 공백으로 구분되어 적혀 있습니다.

출력

최종적인 종이의 모든 칸의 색을 H행으로 출력하세요. i행째 (1 ≦ i ≦ H)에는, W개의 정수를 공백으로 구분하여 출력하세요. 여기서, j번째 (1 ≦ j ≦ W)에 출력하는 정수는 칸 (i, j)의 색입니다.

제한

2 ≦ H ≦ 500.
2 ≦ W ≦ 500.
1 ≦ Q ≦ 200 000.
qk는 1 또는 2 중 하나이다 (1 ≦ k ≦ Q).
qk = 1인 경우, 1 ≦ xk ≦ H - 1, 1 ≦ yk ≦ W - 1, 1 ≦ ck ≦ 109 (1 ≦ k ≦ Q).
qk = 2인 경우, 1 ≦ xk ≦ H - 1, 1 ≦ yk ≦ W - 1 (1 ≦ k ≦ Q).
입력되는 값은 모두 정수이다.

서브태스크

번호 배점 제한
1 32 H = 2, W = 2, qk = 1 (1 ≦ k ≦ Q).
2 32 qk = 1 (1 ≦ k ≦ Q).
3 36 추가 제한 없음.

예제 입력 1

5 5 4
1 2 2 1
2 1 2
2 3 3
1 1 3 5

예제 출력 1

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

4번의 작업을 순서대로 살펴봅시다.

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

따라서, 최종적인 종이의 모든 칸의 색은 출력 예제와 같이 나옵니다.

이 입출력 예제는 서브태스크 3의 제한을 만족합니다.

예제 입력 2

5 5 3
1 1 1 2
1 3 3 3
1 2 4 2

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

이 입출력 예제는 서브태스크 2, 3의 제한을 만족합니다.

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

예제 출력 3

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

이 입출력 예제는 서브태스크 3의 제한을 만족합니다.

댓글을 작성하려면 로그인해야 합니다.