問題文

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

制約

• 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)．
• 入力される値はすべて整数である．

小課題

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 点) 追加の制約はない．

入力例 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 = 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 の制約を満たす．

入力例 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 の制約を満たす．