AT_joi2025_yo2_a マスキングテープ (Masking Tape)

JOI 君は，紙とマスキングテープを使い，色塗りをして遊んでいる． 紙は長方形であり，縦 $ H $ 行，横 $ W $ 列のマス目が描かれている．上から $ i $ 行目 ( $ 1 \leqq i \leqq H $ )，左から $ j $ 列目 ( $ 1 \leqq j \leqq W $ ) のマスをマス $ (i, j) $ と呼ぶ． それぞれのマスには色が $ 1 $ つ定められている．色は整数で表され，はじめすべてのマスの色は $ 0 $ である． JOI 君は，この紙とマスキングテープを用いて $ Q $ 回の操作を行う． $ k $ 回目 ( $ 1 \leqq k \leqq Q $ ) の操作は，整数 $ q_k $ の値に応じて以下のように説明される． - $ q_k = 1 $ のとき，この操作は整数 $ x_k, y_k, c_k $ で表される．マス $ (x_k, y_k) $ , $ (x_k + 1, y_k) $ , $ (x_k, y_k + 1) $ , $ (x_k + 1, y_k + 1) $ それぞれについて，マスがマスキングテープで覆われていなければ，そのマスの色を $ c_k $ に変更する．マスがマスキングテープで覆われているならば，そのマスには何もしない． - $ q_k = 2 $ のとき，この操作は整数 $ x_k, y_k $ で表される．マス $ (x_k, y_k) $ , $ (x_k + 1, y_k) $ , $ (x_k, y_k + 1) $ , $ (x_k + 1, y_k + 1) $ をマスキングテープで覆う． $ Q $ 回の操作が終わった後，すべてのマスキングテープを剥がす．なお，あるマスのマスキングテープを剥がしたとき，そのマスの色はマスキングテープで覆われる直前の色と同じになる． $ Q $ 回の操作の情報が与えられたとき，最終的な紙のすべてのマスの色を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ H $ $ W $ $ Q $ ( $ Query \: 1 $ ) ( $ Query \: 2 $ ) $ \vdots $ ( $ Query \: Q $ ) 各 ( $ Query \: k $ ) ( $ 1 \leqq k \leqq Q $ ) にはいくつかの整数が空白区切りで書かれている．そのうち $ 1 $ 個目の整数が $ q_k $ であり，この行の内容は以下のいずれかである． - $ q_k = 1 $ のとき，この行には続いて $ 3 $ 個の整数 $ x_k, y_k, c_k $ が空白区切りで書かれている． - $ q_k = 2 $ のとき，この行には続いて $ 2 $ 個の整数 $ x_k, y_k $ が空白区切りで書かれている．

最終的な紙のすべてのマスの色を $ H $ 行で出力せよ． $ i $ 行目 ( $ 1 \leqq i \leqq H $ ) には， $ W $ 個の整数を空白区切りで出力せよ．ここで， $ j $ 番目 ( $ 1 \leqq j \leqq W $ ) に出力する整数はマス $ (i, j) $ の色とする．

### 小課題 1. ( $ 32 $ 点) $ H = 2 $ ， $ W = 2 $ ， $ q_k = 1 $ ( $ 1 \leqq k \leqq Q $ )． 2. ( $ 32 $ 点) $ q_k = 1 $ ( $ 1 \leqq k \leqq Q $ )． 3. ( $ 36 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 4 $ 回の操作を順に見ていく． $ 1 $ 回目の操作について， $ q_1 = 1 $ である．マス $ (2, 2) $ ， $ (2, 3) $ ， $ (3, 2) $ ， $ (3, 3) $ はすべてマスキングテープで覆われていないので，色を $ 1 $ に変更する． このとき，紙は以下のようになっている． ``` 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ``` $ 2 $ 回目の操作について， $ q_2 = 2 $ である．マス $ (1, 2) $ ， $ (1, 3) $ ， $ (2, 2) $ ， $ (2, 3) $ をマスキングテープで覆う． このとき，紙は以下のようになっている．なお，マスキングテープで覆ったマスの色を表す整数の右に `*` を付けた． ``` 0 0* 0* 0 0 0 1* 1* 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ``` $ 3 $ 回目の操作について， $ q_3 = 2 $ である．マス $ (3, 3) $ ， $ (3, 4) $ ， $ (4, 3) $ ， $ (4, 4) $ をマスキングテープで覆う． このとき，紙は以下のようになっている． ``` 0 0* 0* 0 0 0 1* 1* 0 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0 ``` $ 4 $ 回目の操作について， $ q_4 = 1 $ である．マス $ (1, 4) $ ， $ (2, 4) $ はマスキングテープで覆われていないので，色を $ 5 $ に変更する．マス $ (1, 3) $ ， $ (2, 3) $ はマスキングテープで覆われているので，何もしない． このとき，紙は以下のようになっている． ``` 0 0* 0* 5 0 0 1* 1* 5 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0 ``` したがって，最終的な紙のすべてのマスの色は出力例のようになっている． この入出力例は小課題 $ 3 $ の制約を満たす． ### Sample Explanation 2 この入出力例は小課題 $ 2, 3 $ の制約を満たす． ### Sample Explanation 3 この入出力例は小課題 $ 3 $ の制約を満たす． ### Constraints - $ 2 \leqq H \leqq 500 $ ． - $ 2 \leqq W \leqq 500 $ ． - $ 1 \leqq Q \leqq 200 \: 000 $ ． - $ q_k $ は $ 1 $ か $ 2 $ のいずれかである ( $ 1 \leqq k \leqq Q $ )． - $ q_k = 1 $ のとき， $ 1 \leqq x_k \leqq H - 1 $ ， $ 1 \leqq y_k \leqq W - 1 $ ， $ 1 \leqq c_k \leqq 10^9 $ ( $ 1 \leqq k \leqq Q $ )． - $ q_k = 2 $ のとき， $ 1 \leqq x_k \leqq H - 1 $ ， $ 1 \leqq y_k \leqq W - 1 $ ( $ 1 \leqq k \leqq Q $ )． - 入力される値はすべて整数である．