配点 : 100 点
問題文
H 行 W 有一个柱子网格,所有的方块最初都是无色的。从网格上方 i 行,从左数 j 选择列中的方块。 当表示为 (i,j) 。也不同于黑色 N 颜色类型 您将收到 1, \dots, N 。
Q 查询,因此请按顺序处理它们并输出网格中每个方块的颜色。查询是 3 采用以下格式之一:
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 绘画 涂有
但是 2 两个方块 给出了 S,T 是 在連結意味着 S,T 不都是黑色的,并且它们被重复地垂直和水平移动到相邻的非黑色方块。 这意味着您可以移至 S 减去 T 。
制約
- 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) 不是黑色
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
H W
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询都是 3 可以采用以下格式之一给出:
1 i l r
2 j l r
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) 的颜色。然而,质量 如果 (i,j) 为黑色,则 0,如果它是无色的 请使用 -1 。
入力例1
3 3 2 3 3 1 1 1 1 2 1 3 3 1 1 2
出力例1
2 2 2 0 0 0 1 1 1
处理每个查询后,网格将如下图所示。
1 在第二个查询中,所有单元格都是连接的,因此所有单元格都有颜色。 它涂有 1 。 2 在第二个查询中,2 该行中的所有单元格都将被涂成黑色。 3 在第二个查询中,1 行中的所有方块均已着色 2 。
入力例2
5 6 4 8 2 2 1 5 3 2 3 3 1 2 1 3 1 4 2 6 3 5 1 1 3 5 6 2 2 5 1 4 3 1 3 4
出力例2
-1 0 4 4 0 3 0 0 0 4 0 3 1 0 4 4 0 3 1 0 0 0 0 0 1 0 2 2 2 2