AT_nupc2024_d.Painting

给定一个 $H$ 行 $W$ 列的网格，初始时所有格子都是无色的。网格中自上而下第 $i$ 行、自左而右第 $j$ 列的格子记为 $(i,j)$。此外，还存在 $N$ 种非黑色的颜色，编号为 $1,\dots,N$。

现有 $Q$ 个操作，依次处理，并输出最后每个格子的颜色。操作有以下三种形式之一：

• 1 i l r：将 $(i,l),(i,l+1),\dots,(i,r)$ 这些格子涂成黑色；
• 2 j u d：将 $(u,j),(u+1,j),\dots,(d,j)$ 这些格子涂成黑色；
• 3 i j c：将与格子 $(i,j)$ 连通的所有格子全部染成颜色 $c$。

这里，两个格子 $S,T$ 被称为连通，当且仅当 $S,T$ 都不是黑色，且可以经由上下左右相邻的、非黑色格子一步步移动，从 $S$ 到达 $T$。

输入以如下格式从标准输入中给出：

$H\ W\ N\ Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个操作皆为下述三种形式之一：

$1\ i\ l\ r$

$2\ j\ u\ d$

$3\ i\ j\ c$

所有操作处理完毕后，将网格每个格子的状态按以下格式输出：

$c_{1,1}\ c_{1,2}\ \dots\ c_{1,W}$
$c_{2,1}\ c_{2,2}\ \dots\ c_{2,W}$
$\vdots$
$c_{H,1}\ c_{H,2}\ \dots\ c_{H,W}$

其中 $c_{i,j}$ 表示格子 $(i,j)$ 的颜色。若格子为黑色，则 $c_{i,j}=0$；若为无色，则 $c_{i,j}=-1$；否则为对应的颜色编号。

样例解释 1

每个操作处理后的网格状态如下图所示：

第 1 条操作时，所有格子连通，因此全部被染成颜色 1。第 2 条操作时，第 2 行全部格子染成黑色。第 3 条操作时，第 1 行全部格子染成颜色 2。

数据范围

• $1\leq H, W$
• $1 \leq H\times W \leq 2\times10^5$
• $1 \leq N, Q \leq 2\times10^5$
• 第 1 类操作中，$1\leq i\leq H,\ 1\leq l\leq r\leq W$
• 第 2 类操作中，$1\leq j\leq W,\ 1\leq u\leq d\leq H$
• 第 3 类操作中，$1\leq i\leq H,\ 1\leq j\leq W,\ 1\leq c\leq N$
• 对于第 3 类操作，处理前 $(i,j)$ 不是黑色
• 所有输入均为整数。

由 ChatGPT 5 翻译