cho.sh

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

시간 제한2초메모리 제한2048 MB

문제

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

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

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

JOI 君は，この紙とマスキングテープを用いて Q 回の操作を行う． k 回目 (1 ≦ k ≦ Q) の操作は，整数 qk の値に応じて以下のように説明される．

  • qk = 1 のとき，この操作は整数 xk, yk, ck で表される．マス (xk, yk), (xk + 1, yk), (xk, yk + 1), (xk + 1, yk + 1) それぞれについて，マスがマスキングテープで覆われていなければ，そのマスの色を ck に変更する．マスがマスキングテープで覆われているならば，そのマスには何もしない．
  • qk = 2 のとき，この操作は整数 xk, yk で表される．マス (xk, yk), (xk + 1, yk), (xk, yk + 1), (xk + 1, yk + 1) をマスキングテープで覆う．

Q 回の操作が終わった後，すべてのマスキングテープを剥がす．なお，あるマスのマスキングテープを剥がしたとき，そのマスの色はマスキングテープで覆われる直前の色と同じになる．

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

입력

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

H W Q
(Query 1)
(Query 2)
:
(Query Q)

各 (Query k) (1 ≦ k ≦ Q) にはいくつかの整数が空白区切りで書かれている．そのうち 1 個目の整数が qk であり，この行の内容は以下のいずれかである．

  • qk = 1 のとき，この行には続いて 3 個の整数 xk, yk, ck が空白区切りで書かれている．
  • qk = 2 のとき，この行には続いて 2 個の整数 xk, yk が空白区切りで書かれている．

출력

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

제한

  • 2 ≦ H ≦ 500．
  • 2 ≦ W ≦ 500．
  • 1 ≦ Q ≦ 200 000．
  • qk は 1 か 2 のいずれかである (1 ≦ k ≦ Q)．
  • qk = 1 のとき，1 ≦ xk ≦ H - 1，1 ≦ yk ≦ W - 1，1 ≦ ck ≦ 109 (1 ≦ k ≦ Q)．
  • qk = 2 のとき，1 ≦ xk ≦ H - 1，1 ≦ yk ≦ W - 1 (1 ≦ k ≦ Q)．
  • 入力される値はすべて整数である．