D - Painting Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 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