AT_pakencamp_2019_day3_e 大きなクリスマスプレゼント

[problemUrl]: https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_e 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 の外にプレゼントが一部でも出るような移動はしてはなりません． それぞれのプレゼント配りで，最終的なプレゼントの位置として考えられるものは何種類あるかを求めてください．

入力は以下の形式で標準入力から与えられます． > $ 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\ \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 $ 個のマスに建物は一つもない ### 部分点 この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます． 提出したソースコードの得点は，正解した小課題の点数の合計となります． 1. (13 点) $ H\ =\ 1 $，$ W\ \leq\ 200 $，$ Q\ =\ 1 $ で，プレゼントの一辺の長さ $ L_i $ は全て $ 1 $ である． 2. (13 点) $ H\ \leq\ 200 $，$ W\ \leq\ 200 $，$ Q\ =\ 1 $ で，プレゼントの一辺の長さ $ L_i $ は全て $ 1 $ である． 3. (19 点) プレゼントの一辺の長さ $ L_i $ は全て $ 1 $ である． 4. (11 点) $ H\ \leq\ 200 $，$ W\ \leq\ 200 $，$ Q\ =\ 1 $ である． 5. (11 点) $ H\ \leq\ 200 $，$ W\ \leq\ 200 $，$ Q\ \leq\ 1\ 000 $ である． 6. (11 点) $ H\ \leq\ 200 $，$ W\ \leq\ 200 $ である． 7. (22 点) 追加の制約はない． ### Sample Explanation 1 この入力例は小課題 1 の制約を満たします． プレゼントは、最初の位置を含めて，以下のような $ 3 $ つの位置に動かすことができます． !\[ \](https://img.atcoder.jp/pakencamp-2019-day3/d036ed6e5b6c2dc98a24f9f2840451e6.png) ### Sample Explanation 2 この入力例は小課題 2 の制約を満たします． プレゼントは $ 12 $ つの位置に動かすことができます．