第24回日本情報オリンピック　二次予選

2024年12月10日
情報オリンピック日本委員会

問題文

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

小課題

1. (32 点) H = 2，W = 2，q_{k = 1} (1 ≦ k ≦ Q)．
2. (32 点) q_{k = 1} (1 ≦ k ≦ Q)．
3. (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) の色とする．

入出力例

入力例 1
5 5 4
1 2 2 1
2 1 2
2 3 3
1 1 3 5

出力例 1
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

4 回の操作を順に見ていく．

1 回目の操作について，q₁ = 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 である．マス (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₃ = 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₄ = 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 の制約を満たす．

入力例 2
5 5 3
1 1 1 2
1 3 3 3
1 2 4 2

出力例 2
2 2 0 0 0
2 2 0 2 2
0 0 3 2 2
0 0 3 3 0
0 0 0 0 0

この入出力例は小課題 2, 3 の制約を満たす．

入力例 3
10 10 10
2 5 7
2 5 6
1 5 6 1
1 9 2 1
2 1 1
1 2 4 2
2 3 2
1 2 2 3
1 9 9 2
1 8 8 1

出力例 3
0 0 0 0 0 0 0 0 0 0
0 0 3 2 2 0 0 0 0 0
0 0 0 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 1 1 2
0 1 1 0 0 0 0 0 2 2

この入出力例は小課題 3 の制約を満たす．