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 翻译