题目描述

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$ 分）无额外限制。

输入格式

输入按以下格式给出：

$$ \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$ 的限制。