爆破計画 COBOL(Beta)編（paizaランク A 相当）

H 行 W 列のグリッドがあり、各マスは . か # のいずれかです。
上から i 行目、右から j 列目をマス (i,j) と表します。
このグリッド上に海賊団が N 個の爆弾を設置しました。
i (1 ≦ i ≦ N) 番目の爆弾はマス (p_i,q_i) に設置され、威力は r_i で、爆弾 i と名づけられています。

paiza くんは爆弾の爆破計画を入手しました。
この爆破計画では j = 1, 2, ... , K の順に以下の手順が行われます。
1. 爆弾の有無の確認: 爆弾 X_j がグリッド上にあるなら次の 2~4 の手順を行います。爆弾 X_j がグリッド上にないなら、次の爆弾の 1. の手順に進みます。

2. 爆破: この手順開始時に爆弾 X_j のあるマスと同じ行または同じ列にあり、爆弾 X_j のあるマスとのマンハッタン距離が爆弾の威力以下の全てのマスを爆破します。
　　より厳密には、爆弾 X_j のあるマス (p, q) としたとき、(a = p かつ |b - q| ≦ r_{X_j}) または (b = q かつ |a - p| ≦ r_{X_j}) を満たすマス (a, b) をすべて爆破します。爆破されたマスは空きマスとなります (空きマスは . とも # とも異なるマスとします)。

3. 連鎖爆破: 手順 2. で爆破されたマス(空きマス)に別の爆弾が存在する場合、その爆弾も連鎖的に爆破操作を行います。この処理を連鎖的に爆破される爆弾がなくなるまで繰り返します。

4. 落下: 全ての連鎖爆破が終了した後、以下の規則に従って空きマスの上にあるマスを落下させます。
各列 b = 1, 2, ... , W について a = H, H-1, ... , 1 の順に以下の手順が行われます。
マス (a,b) が空きマスであるなら次の処理を行う。1 ≦ a' < a かつ マス (a',b) が空きマスでないような最大の a' を A とする。
・ そのような A が存在するとき、マス (a,b) を マス (A,b) で置き換える。その後、マス (A,b) を空きマスに置き換える。
・ そのような A が存在しないとき、マス (a,b) を . に置き換える。

すべての爆破計画の手順が完了した後のグリッドの状態を出力してください。
ただし、爆弾があるマスは $ で表すものとします。

なお、以下の制約に注意してください。
・ 1 ≦ H, W ≦ 10^5
・ 1 ≦ H×W ≦ 10^5

空きマスを o で表すとしたとき、3 行 1 列のグリッドの落下操作の手順を示します。

 #    #    o    .
 . -> o -> # -> #
 o    .    .    .

空きマスを o、爆弾があるマスを $ とすると、入力例 1 では以下のように爆破計画が実行されます。

 ##.##   爆破  ##o##  落下  #...#
 .#$.#  --->  .ooo#  --->  .#.##
 #.##.        #.o#.        #..#.

入力例 2 では以下のように爆破計画が実行されます。

 #####        #####  連鎖  #####        .....
 #####  爆破   ###o#  爆破  ###o#  落下   #.#.#
 ##.##  --->  ##.o#  --->  #o.o#  --->  #.#.#
 .$#$#        .oooo        ooooo        ##..#
 #.##.        #.#o.        #o#o.        ####.

入力例 4 では以下のように爆破計画が実行されます。

 #$#$  爆破  #$#$  落下    #...  爆破  #..o
 .###  --->  .#o#  --->  .$.$  --->  .$oo
 #.$#        #ooo        ####        ###o

 落下  #...   爆破  #o..   落下  ....
 --->  .$..  --->  ooo.  --->  #...
       ###.        #o#.        #.#.