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

JOI 君は,紙とマスキングテープを使い,色塗りをして遊んでいる.

紙は長方形であり,縦 H 行,横 W 列のマス目が描かれている.上から i 行目 ( 1 ≦ i ≦ H ),左から j 列目 ( 1 ≦ j ≦ W ) のマスをマス (i, j) と呼ぶ.

それぞれのマスには色が 1 つ定められている.色は整数で表され,はじめすべてのマスの色は 0 である.

JOI 君は,この紙とマスキングテープを用いて Q 回の操作を行う.
k 回目 ( 1 ≦ k ≦ 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 回の操作の情報が与えられたとき,最終的な紙のすべてのマスの色を求めるプログラムを作成せよ.

2 ≦ H ≦ 500 .

2 ≦ W ≦ 500 .

1 ≦ Q ≦ 200 000 .

q k は 1 か 2 のいずれかである ( 1 ≦ k ≦ Q ).

q k = 1 のとき, 1 ≦ x k ≦ H - 1 , 1 ≦ y k ≦ W - 1 , 1 ≦ c k ≦ 10 9 ( 1 ≦ k ≦ Q ).

q k = 2 のとき, 1 ≦ x k ≦ H - 1 , 1 ≦ y k ≦ W - 1 ( 1 ≦ k ≦ Q ).

入力される値はすべて整数である.

( 32 点) H = 2 , W = 2 , q k = 1 ( 1 ≦ k ≦ Q ).

( 32 点) q k = 1 ( 1 ≦ k ≦ Q ).

( 36 点) 追加の制約はない.

入力は以下の形式で与えられる.

H W Q

( Query 1 )

( Query 2 )

:

( Query Q )

各 ( Query k ) ( 1 ≦ k ≦ 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 ≦ i ≦ H ) には, W 個の整数を空白区切りで出力せよ.ここで, j 番目 ( 1 ≦ j ≦ W ) に出力する整数はマス (i, j) の色とする.

생성자가 기록되지 않았습니다.

출처 JOI 2025 Preliminary 2