종이는 직사각형이며, 세로 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)을 마스킹 테이프로 덮습니다.
이때, 종이는 다음과 같이 됩니다. 단, 마스킹 테이프로 덮은 칸의 색을 나타내는 정수의 오른쪽에 '*'를 붙였습니다.
hanzch 1년 전
마스킹 테이프 (Masking Tape) 서브태스크 다국어
문제
JOI 군은 종이와 마스킹 테이프를 사용하여 색칠하며 놀고 있습니다.
종이는 직사각형이며, 세로 H행, 가로 W열의 격자가 그려져 있습니다. 위에서부터 i행째 (1 ≦ i ≦ H), 왼쪽에서부터 j열째 (1 ≦ j ≦ W)의 칸을 칸 (i, j)라고 부릅니다.
각 칸에는 하나의 색이 정해져 있습니다. 색은 정수로 표현되며, 처음에는 모든 칸의 색이 0입니다.
JOI 군은 이 종이와 마스킹 테이프를 이용하여 Q번의 작업을 수행합니다. k번째 (1 ≦ k ≦ Q) 작업은 정수 qk의 값에 따라 다음과 같이 설명됩니다.
Q번의 작업이 끝난 후, 모든 마스킹 테이프를 제거합니다. 특정 칸의 마스킹 테이프를 제거했을 때, 그 칸의 색은 마스킹 테이프로 덮이기 직전의 색과 동일하게 됩니다.
Q번의 작업 정보가 주어졌을 때, 최종적으로 종이의 모든 칸의 색을 구하는 프로그램을 작성하세요.
입력
입력은 다음 형식으로 주어집니다.
각 (Query k) (1 ≦ k ≦ Q)에는 몇 개의 정수가 공백으로 구분되어 적혀 있습니다. 그 중 첫 번째 정수가 qk이며, 이 행의 내용은 다음 중 하나입니다.
출력
최종적인 종이의 모든 칸의 색을 H행으로 출력하세요. i행째 (1 ≦ i ≦ H)에는, W개의 정수를 공백으로 구분하여 출력하세요. 여기서, j번째 (1 ≦ j ≦ W)에 출력하는 정수는 칸 (i, j)의 색입니다.
제한
서브태스크
예제 입력 1
예제 출력 1
4번의 작업을 순서대로 살펴봅시다.
1번째 작업에서, q1 = 1입니다. 칸 (2, 2), (2, 3), (3, 2), (3, 3)은 모두 마스킹 테이프로 덮여있지 않으므로, 색을 1로 변경합니다.
이때, 종이는 다음과 같이 됩니다.
2번째 작업에서, q2 = 2입니다. 칸 (1, 2), (1, 3), (2, 2), (2, 3)을 마스킹 테이프로 덮습니다.
이때, 종이는 다음과 같이 됩니다. 단, 마스킹 테이프로 덮은 칸의 색을 나타내는 정수의 오른쪽에 '*'를 붙였습니다.
3번째 작업에서, q3 = 2입니다. 칸 (3, 3), (3, 4), (4, 3), (4, 4)를 마스킹 테이프로 덮습니다.
이때, 종이는 다음과 같이 됩니다.
4번째 작업에서, q4 = 1입니다. 칸 (1, 4), (2, 4)는 마스킹 테이프로 덮여있지 않으므로, 색을 5로 변경합니다. 칸 (1, 3), (2, 3)은 마스킹 테이프로 덮여있으므로, 아무것도 하지 않습니다.
이때, 종이는 다음과 같이 됩니다.
따라서, 최종적인 종이의 모든 칸의 색은 출력 예제와 같이 나옵니다.
이 입출력 예제는 서브태스크 3의 제한을 만족합니다.
예제 입력 2
예제 출력 2
이 입출력 예제는 서브태스크 2, 3의 제한을 만족합니다.
예제 입력 3
예제 출력 3
이 입출력 예제는 서브태스크 3의 제한을 만족합니다.