题目描述

JOI 君正在用纸和遮蔽胶带涂色，很有趣。

纸张呈矩形，有 $H$ 行 $W$ 列。位于第 $i$ 行（$1 \leq i\leq H$）第 $j$ 列（$1 \leq j \leq W$）的正方形称为正方形 $(i,j)$。

每个方块都被分配了一种颜色。颜色用整数表示，最初所有方块的颜色都是 $0$。

JOI 君将使用纸和遮蔽胶带进行 $Q$ 次操作。根据整数 $q_k$ 的值， 第 $k$ 次（$1 \leq k \leq Q$）操作如下。

• 当 $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$ 次操作的信息，编写一个程序来找出纸上所有方块的最终颜色。

输入格式

输入格式如下：

$$\begin{aligned} &H\ W\ Q\\ &query_1\\ &query_2\\ & \vdots\\ &query_Q \end{aligned} $$

其中对于询问 $query_k$，先输入 $q_k$，如果 $q_k=1$ 则输入 $x_k,y_k,c_k$，否则输入 $x_k,y_k$。

输出格式

输出一个 $H\times W$ 的矩阵，表示纸张最终的颜色。

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

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

5 5 3
1 1 1 2
1 3 3 3
1 2 4 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

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

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

提示

数据范围

对于 $100\%$ 的数据，$2\leq H,W\leq 500$，$1\leq Q\leq 200 000$。$q_k$ 为 $1$ 或 $2(1 \leq k \leq Q)$。$1\leq x_k\leq H- 1,1 \leq y_k \leq W - 1,1\leq c_k \leq 10^9$。

子任务：

1. （32 分）$H = 2，W = 2，q_k = 1$
2. （32 分）$q_k=1$
3. （36 分）无其他限制。