문제
JOI 군은 종이와 마스킹 테이프를 사용하여 색칠 놀이를 하고 있다.
종이는 직사각형 모양이며, 세로 $H$행, 가로 $W$열의 격자가 그려져 있다. 위에서 $i$번째 행 ($1 \le i \le H$), 왼쪽에서 $j$번째 열 ($1 \le j \le W$)에 있는 칸을 칸 $(i, j)$라고 부른다.
각 칸에는 색이 $1$개씩 정해져 있다. 색은 정수로 나타내며, 처음에 모든 칸의 색은 $0$이다.
JOI 군은 이 종이와 마스킹 테이프를 사용하여 $Q$번의 작업을 수행한다. $k$번째 ($1 \le k \le 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$번의 작업 정보가 주어졌을 때, 최종적인 종이의 모든 칸의 색을 구하는 프로그램을 작성하시오.
제한
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$는 $1$ 또는 $2$ 중 하나이다 ($1 \le k \le Q$).
- $q_k = 1$일 때, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$, $1 \le c_k \le 10^9$ ($1 \le k \le Q$).
- $q_k = 2$일 때, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- 입력되는 값은 모두 정수이다.
섭태스크
- ($32$점) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$점) $q_k = 1$ ($1 \le k \le Q$).
- ($36$점) 추가 제한 없음.
입력
입력은 다음 형식으로 주어진다.
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
각 $(\text{Query } k)$ ($1 \le k \le Q$)에는 몇 개의 정수가 공백으로 구분되어 적혀 있다. 그중 $1$번째 정수가 $q_k$이며, 이 줄의 내용은 다음 중 하나이다.
- $q_k = 1$일 때, 이 줄에는 이어서 $3$개의 정수 $x_k, y_k, c_k$가 공백으로 구분되어 적혀 있다.
- $q_k = 2$일 때, 이 줄에는 이어서 $2$개의 정수 $x_k, y_k$가 공백으로 구분되어 적혀 있다.
출력
최종적인 종이의 모든 칸의 색을 $H$줄에 걸쳐 출력하시오. $i$번째 줄 ($1 \le i \le H$)에는 $W$개의 정수를 공백으로 구분하여 출력하시오. 여기서 $j$번째 ($1 \le j \le W$)로 출력하는 정수는 칸 $(i, j)$의 색이다.
입출력 예제
입력 예제 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$번째 작업에 대하여, $q_1 = 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$번째 작업에 대하여, $q_2 = 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$번째 작업에 대하여, $q_3 = 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$번째 작업에 대하여, $q_4 = 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$의 제한을 만족한다.