마스킹 테이프

문제

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$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($32$ 점) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
2. ($32$ 점) $q_k = 1$ ($1 \le k \le Q$).
3. ($36$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$H$ $W$ $Q$
($Query\,1$)
($Query\,2$)
$:$
($Query\,Q$)

각 ($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$ 의 제약을 만족한다.