---
tags: 問題
---

# Walking-2D

実行時間制限 : 2sec / メモリ制限 : 1024MB

配点 : $400$点

## 問題文

縦$H$マス、横$W$マスの文字で構成されている配列$S$が与えられます。文字$S_{i,j} \left(1 \leq i \leq H , 1 \leq j \leq W\right)$は```#```のときは壁のマスを、```.```のときは道のマスを表しています。

太郎くんは$S$の上を上下左右に何回でも移動できます。ただし、道の上しか移動ができず、壁は乗り越えることができません。また斜め移動もできません。

このとき、以下の$Q$個のクエリに答えてください。

太郎くんのスタート地点の座標が$\left(x,y\right)$のとき、移動できるマスは何個存在しますか？

## 制約

* $1\leq H×W \leq 2×10^5$
* $S_i$は```#```または```.```からなる長さ$W$の文字列
* $S$は少なくとも１つの```.```を含む
* $1 \leq Q \leq 2×10^5$
* $1 \leq x \leq W$
* $1 \leq y \leq H$
* $S_{y,x} =$ ```.```

入力はすべて正の整数

## 入力

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

H W
S_1
S_2
...
S_H
Q
x_1 y_1
x_2 y_2
...
x_Q y_Q

## 出力

それぞれのクエリに対して太郎くんが移動できるマス目の数を出力してください。

## 入力例1

4 6
...#.#
##.###
..##.#
.#....
3
2 1
5 3
1 4

## 出力例1

4
5
3

スタート地点も移動できるマスに含みます。

## 入力例2

4 5
.####
....#
##.##
#....
2
2 4
4 2

## 出力例2

10
10

## 入力例3

1 15
..#....#.###...
4
1 1
6 1
15 1
7 1

## 出力例3

2
4
3
4