33173번 - マスキングテープ (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 回の操作の情報が与えられたとき,最終的な紙のすべてのマスの色を求めるプログラムを作成せよ.

입력

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

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) の色とする.

제한

• 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⁹ (1 ≦ k ≦ Q).
• q_k = 2 のとき,1 ≦ x_k ≦ H - 1,1 ≦ y_k ≦ W - 1 (1 ≦ k ≦ Q).
• 入力される値はすべて整数である.

서브태스크

힌트