/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
PAKEN City は，南北に H メートル，東西に W メートルの長方形の形をしています．これは南北に 1 メートルずつ，東西に 1 メートルずつに区切られた H \times W 個のマスに分けられており，北から i 番目，西から j 番目のマスを (i, j) で表します．
PAKEN City のいくつかのマスには建物が建っていて通れません，それ以外のマスは通行可能なマスです．より具体的には，S_{i, j} が # のとき建物が建っていて通れないことを表し，. のとき通行可能であることを表します．
サンタクロースの E869120 君は，パ研王国にプレゼントを Q 回配ることにしました．
i 回目のプレゼント配りは次のようになっています．
- 最初，マス (X_i, Y_i) を左上のマスとして，一辺 L_i メートルの正方形の形をしたプレゼントが置かれている．
- その後，プレゼントを移動することができる．より具体的には，「建物と重ならないように，プレゼントを回転させずに，東西南北のいずれかの方向にちょうど 1 メートル動かす」操作を何回か (0 回でも良い) 行う．
ただし，PAKEN City の外にプレゼントが一部でも出るような移動はしてはなりません．
それぞれのプレゼント配りで，最終的なプレゼントの位置として考えられるものは何種類あるかを求めてください．
制約
- 1 \leq H \leq 1 \ 500
- 1 \leq W \leq 1 \ 500
- 1 \leq Q \leq 150 \ 000
- H, W, Q はすべて整数である
- Q 個すべてのプレゼントの最初の位置は PAKEN City の内部にあり，その L_i^2 個のマスに建物は一つもない
部分点
この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．
- (13 点) H = 1，W \leq 200，Q = 1 で，プレゼントの一辺の長さ L_i は全て 1 である．
- (13 点) H \leq 200，W \leq 200，Q = 1 で，プレゼントの一辺の長さ L_i は全て 1 である．
- (19 点) プレゼントの一辺の長さ L_i は全て 1 である．
- (11 点) H \leq 200，W \leq 200，Q = 1 である．
- (11 点) H \leq 200，W \leq 200，Q \leq 1 \ 000 である．
- (11 点) H \leq 200，W \leq 200 である．
- (22 点) 追加の制約はない．
入力
入力は以下の形式で標準入力から与えられます．
H W
S_{1, 1} S_{1, 2} S_{1, 3} \cdots S_{1, W}
S_{2, 1} S_{2, 2} S_{2, 3} \cdots S_{2, W}
S_{3, 1} S_{3, 2} S_{3, 3} \cdots S_{3, W}
: : :
S_{H, 1} S_{H, 2} S_{H, 3} \cdots S_{H, W}
Q
X_1 Y_1 L_1
X_2 Y_2 L_2
X_3 Y_3 L_3
: :
X_Q Y_Q L_Q
出力
最初のプレゼント配りから順に，最終的なプレゼントの位置としてありうるものの種類数を，1 行ずつ出力してください．
入力例 1
1 10 .#..##...# 1 1 7 1
出力例 1
3
この入力例は小課題 1 の制約を満たします．
プレゼントは、最初の位置を含めて，以下のような 3 つの位置に動かすことができます．
入力例 2
6 5 #..#. ..#.. #.#.. ..#.. .#..# .#... 1 3 4 1
出力例 2
12
この入力例は小課題 2 の制約を満たします．
プレゼントは 12 つの位置に動かすことができます．
入力例 3
8 8 ....#... ..#..... ......#. #....... ...#.... .#...... .....#.. .......# 6 4 5 1 1 6 2 2 5 2 7 1 2 4 6 3 6 3 3
出力例 3
56 2 14 6 2 1