Problem H： Puzzle and Hexagons

Backgorund

超大人気ゲーム「パズル&ヘキサゴンズ」がついにリリースされた。このゲームは超面白すぎてドハマりする人が続出。あまりの熱中度に医師から中毒認定を受ける者も続出した。世界各国の有志達はこのゲームの中毒者達を助けるために「パズル&ヘキサゴンズ」のシミュレータを作り、危険な実機でのプレイを避けるよう促そうとした。あなたにはシミュレータ作りに協力して欲しい。

Problem

正六角形のマスを縦にH個、横にW個敷き詰めた盤面が与えられる。 Fig.1はH=4,W=7の時の盤面とそれに対応するマスの座標(x,y)を示す。


Fig.1

初期状態で各マスには色のついたブロックが存在する。 ブロックの色は以下のようにアルファベット一文字で表現される。

次に操作の数Qが与えられる。

各操作では回転の中心座標(x,y)が与えられ、そのマスの周囲にある6つのブロックを時計回りに一つ回転させることを示す。(Fig.2 参照)。 このとき、ブロックが存在しないマスも空のブロックが存在すると考えて時計回りに一つ回転させる。 ただし、指定された座標とその周辺の６つのマスの内いずれか一つでもH×Wの盤面の中に存在していない場合は回転を行わない。


Fig.2

次に以下の処理ができなくなるまで繰り返す。

  1. Fig.3において、ブロックAの位置からB, C, Dの位置のいずれのマスにもブロックが存在しないとき、ブロックAはCの位置に落下する。マスB, Dが存在しない場合はブロックも存在しないと考え、マスCが存在しない場合は落下の処理を行わない。
  2. 1の処理が可能なブロックが存在する場合は1に戻る。
  3. 同じ色のブロックが3つ以上繋がっている場合、そのブロックは全て消滅する。 2つのブロックが繋がるとはマスの一辺を共有することである。

注意：この一連の処理は、操作が一つも与えられていない状態（初期状態）でも行われる。


Fig.3

全ての操作を実行した後の最終的な盤面を出力せよ。

Input

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

H W
F0,H−1 F1,H−1 … FW−1,H−1
F0,H−2 F1,H−2 … FW−1,H−2
.
.
.
F0,0 F1,0 … FW−1,0
Q
x0 y0
x1 y1
.
.
.
xQ−1 yQ−1

1行目に、盤面の縦と横のサイズを表す2つの整数HとWが与えられる。 2行目からH+1行目に、各添字に対応する盤面の色を表す文字列が与えられる。 H+2行目に、操作の数Qが与えられる。 続くQ行に回転の中心のマスの座標を表すxとyが与えられる。

Constraints

Output

全ての操作を行った後の盤面をH行で出力せよ。 ただし、ブロックが無いマスは'.'で表すこと。

Sample Input1

3 3
RGR
RBP
YEB
1
1 1

Sample Output1

…
YBG
EBP

Fig.4はSample Input1における状態の遷移を表したものである。


Fig.4

Sample Input2

4 5
BYYGG
RRRRR
RRBRR
YYGGB
2
3 1
3 1

Sample Output2

.....
.....
.....
B.BGB

Sample Input3

4 4
BEEP
ERYY
BBRP
RBYP
1
1 2

Sample Output3

....
....
....
.B..

盤面の初期状態ですでに消えるブロックがあること注意。 両端にあるブロックの落下処理に注意。