AT_nupc2024_d Painting

$ 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 $ へ移動できることをいいます。

入力は以下の形式で標準入力から与えられます。 > $ 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 $ としてください。

### Sample Explanation 1 各クエリを処理した後のグリッドの状態は以下の図のようになります。  $ 1 $ つ目のクエリでは、すべてのマスが連結なので、すべてのマスが色 $ 1 $ で塗られます。 $ 2 $ つ目のクエリでは、 $ 2 $ 行目のマスすべてが黒色で塗られます。 $ 3 $ つ目のクエリでは、 $ 1 $ 行目のマスすべてが色 $ 2 $ で塗られます。 ### Constraints - $ 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) $ は黒でない - 入力はすべて整数