問題文

$H \times W$ の大きさのクロスワードがあります。
フレロビくんはクロスワードを作ったので、解いてもらうことにしました。 解くことになったラドくんは、思いついたカギから埋めることにしました。

$H \times W$ の盤面が、 $H$ 個の文字列 $S_1,S_2,\cdots,S_H$ によって与えられます。
上から $i$ 番目、左から $j$ 番目のマスは、 $S_i$ の $j$ 文字目が # の場合は黒マス、 . の場合は白マスです。

クエリが $Q$ 個与えられます。
$i$ 番目のクエリでは、カギの添字 $K_i$ と向き $D_i$ と答え $A_i$ が与えられるので、そのカギを実際に埋めてください。
ここで、$D_i$ は 0 の時は横のカギ、 1 の時は縦のカギであることを表します。
各クエリでは、クロスワードが成立しなくなるカギは与えられないことが保証されます。

各クエリごとに現在の盤面を出力してください。

ただし、カギのある位置は、次の条件のいずれかを満たすものとします。

• 横のカギ: そのマスが白マスかつ、そのマスの左が黒マスまたは盤面の外であり、そのマスの右が白マスである。
• 縦のカギ: そのマスが白マスかつ、そのマスの上が黒マスまたは盤面の外であり、そのマスの下が白マスである。

横のカギと縦のカギが重複する場合があることに注意してください。その場合はどちらも同じ添字を使います。
また、カギの添字は1から始まり、盤面の上側の方が小さく、同じ行では左側が小さいものとします。

クロスワードが成立しているとは、次の条件をどちらも満たすものとします。

• それぞれのカギについて、文字列の長さとそこから連続する白マスの数が等しい。
• それぞれのカギに文字列を当てはめたとき、横のカギと縦のカギが重なる部分は同じ文字である。

この問題の制約上では、カギが少なくとも1つは存在します。

制約

• $2 \le H,W \le 30$
• $Q$ は横のカギと縦のカギの総数に等しい(添字の最大値とは異なる)
• $S_i$ は # または . で構成される長さ $W$ の文字列
• $H,W,Q$ は整数
• $S$ に . が少なくとも2つはある
• 全ての . には少なくとも上下左右のいずれかに他の . が隣接している
• $K$ は整数
• $D$ は 0 または 1 である
• $A$ は英小文字で構成される文字列
• $K,D,A$ の組に盤面のカギとして不正なものはない
• 同じ $K,D$ の組は与えられない

入力

$H\ W$
$S_1$
$S_2$
$\vdots$
$S_H$
$Q$
$K_1\ D_1\ A_1$
$K_2\ D_2\ A_2$
$\vdots$
$K_Q\ D_Q\ A_Q$

出力

$Q \times H$ 行出力してください。 各クエリでは、これまでのカギを当てはめた状態の盤面を出力してください。

最後に改行してください。

サンプル

3 5
#####
#...#
#####
1
1 0 key

#####
#key#
#####

4 4
....
.#.#
##.#
....
4
2 1 cool
1 0 nice
1 1 no
3 0 well

..c.
.#o#
##o#
..l.
nice
.#o#
##o#
..l.
nice
o#o#
##o#
..l.
nice
o#o#
##o#
well