007 - 島の創造

問題

広い広い海に島がいくつかあります。

島の情報は以下のように'.'が海、'#'が島を意味するマップとして与えられます。

.#.#.
.#..#
.##.#

上から $i$ 行目、左から $j$ 行目のマスを ( $i$, $j$ ) で表し、左上隅のマスは ( 1, 1 ) です。

YDKはこの海に新たに島を出現させることでさらに島を拡張することにしました。

彼が知りたいのは任意の島の面積です。

ここで、島の面積は上下左右の4方向で陸続きになっているマスの数とします。
例えば上の例では「面積4の島」「面積1の島」「面積2の島」があります。

「指定したマスに島を出現させるクエリ」と「その時点での島の面積を問うクエリ」が与えられるので、その処理をするプログラムを作ってください。

入力

H W Q
m1,1 m1,2 ... m1,w
  :
mH,1 mH,2 ... mH,w
query1
  :
queryQ

1行目に、マップの縦と横の長さ $H$, $W$ , クエリの数 $Q$ が与えられる。
続く $H$ 行 $W$ 列にマップの情報 $m$_$i$,$j$ が与えられる。
以下、$Q$ 行にわたってクエリが入力される。

クエリは次の2種類がある。

0 i j
(i, j)に島を出現させる。

1 i j
(i, j)の島の面積を出力する。
島がない場合は、0を出力する。

出力

各出力クエリごとに、島の面積を1行に出力する。

制約

• 1 ≤ $H$, $W$ ≤ 1000
• 1 ≤ $Q$ ≤ 500,000
• 1 ≤ $i$ ≤ $H$
• 1 ≤ $j$ ≤ $W$
• すでに島があるマスへの島出現クエリはない。

入出力例

入力例1

3 7 3
####.##
#....##
...####
1 1 4
0 1 5
1 1 4

出力例1

5
14

最初のクエリは、( 1, 4 ) の島の面積を尋ねている。この時の面積は5である。
次のクエリで、( 1, 5 ) に島を出現させる。ここで左の島と右の島が陸続きになる。
クエリ3で、再度( 1, 4 ) の島の面積を出力する。陸続きになったため、最初よりも増えて面積は14である。

入力例2

8 23 7
#######################
#.###.##.....###.####.#
##.#.###.####.##.###.##
###.####.####.##....###
###.####.####.##.##.###
###.####.####.##.###.##
###.####.....###.####.#
#######################
1 3 3
1 7 7
0 2 9
0 7 9
1 8 9
0 7 10
1 7 19

出力例2

0
128
130
147

ほげ

通常の cin, cout だとTLEになるかもしれません。
(入出力の量が多い問題は気をつけようね!)