Task
JOI-kun is playing a coloring game using a sheet of paper and masking tape.
The sheet of paper is rectangular, with a grid of $H$ rows and $W$ columns drawn on it. The cell at the $i$-th row from the top ($1 \le i \le H$) and the $j$-th column from the left ($1 \le j \le W$) is called cell $(i, j)$.
Each cell is assigned $1$ color. Colors are represented by integers, and initially the color of every cell is $0$.
JOI-kun performs $Q$ operations using this sheet of paper and masking tape. The $k$-th operation ($1 \le k \le Q$) is described as follows depending on the value of the integer $q_k$:
- When $q_k = 1$, this operation is represented by integers $x_k, y_k, c_k$. For each of the cells $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$, and $(x_k + 1, y_k + 1)$, if the cell is not covered with masking tape, change the color of that cell to $c_k$. If the cell is covered with masking tape, do nothing to that cell.
- When $q_k = 2$, this operation is represented by integers $x_k, y_k$. Cover the cells $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$, and $(x_k + 1, y_k + 1)$ with masking tape.
After all $Q$ operations are finished, all masking tape is peeled off. Note that when the masking tape on a cell is peeled off, the color of that cell becomes the same as its color just before it was covered with masking tape.
Given the information of the $Q$ operations, write a program to find the final colors of all cells of the sheet of paper.
Constraints
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ is either $1$ or $2$ ($1 \le k \le Q$).
- When $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$).
- When $q_k = 2$, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- All input values are integers.
Subtasks
- ($32$ points) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ points) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ points) No additional constraints.
Input
Input is given in the following format:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Each $(\text{Query } k)$ ($1 \le k \le Q$) contains several space-separated integers. The $1$-st integer is $q_k$, and the content of this line is one of the following:
- When $q_k = 1$, this line is followed by $3$ space-separated integers $x_k, y_k, c_k$.
- When $q_k = 2$, this line is followed by $2$ space-separated integers $x_k, y_k$.
Output
Output the final colors of all cells of the sheet of paper in $H$ lines. On the $i$-th line ($1 \le i \le H$), output $W$ space-separated integers, where the $j$-th integer ($1 \le j \le W$) is the color of cell $(i, j)$.
Samples
Sample Input 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Sample Output 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
Let us examine the $4$ operations in order.
For the $1$-st operation, $q_1 = 1$. Since cells $(2, 2)$, $(2, 3)$, $(3, 2)$, and $(3, 3)$ are all not covered with masking tape, change their colors to $1$.
At this time, the sheet of paper looks as follows:
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
For the $2$-nd operation, $q_2 = 2$. Cover cells $(1, 2)$, $(1, 3)$, $(2, 2)$, and $(2, 3)$ with masking tape.
At this time, the sheet of paper looks as follows. Note that * is attached to the right of the integer representing the color of a cell covered with masking tape:
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
For the $3$-rd operation, $q_3 = 2$. Cover cells $(3, 3)$, $(3, 4)$, $(4, 3)$, and $(4, 4)$ with masking tape.
At this time, the sheet of paper looks as follows:
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
For the $4$-th operation, $q_4 = 1$. Since cells $(1, 4)$ and $(2, 4)$ are not covered with masking tape, change their colors to $5$. Since cells $(1, 3)$ and $(2, 3)$ are covered with masking tape, do nothing to them.
At this time, the sheet of paper looks as follows:
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
Therefore, the final colors of all cells of the sheet of paper are as shown in the sample output.
This sample satisfies the constraints of Subtask $3$.
Sample Input 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Sample Output 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
This sample satisfies the constraints of Subtasks $2, 3$.
Sample Input 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
Sample Output 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
This sample satisfies the constraints of Subtask $3$.