【题目描述】

小蓝最近在整理一张海岛地图。地图可以看成一个 $n$ 行 $m$ 列的方格图，每个方格要么是陆地，要么是海水。

其中：

• # 表示陆地；
• . 表示海水。

如果两个陆地方格有公共边，也就是上下左右相邻，那么它们属于同一个岛屿。一个岛屿的面积等于这个岛屿中陆地方格的数量。

现在小蓝会提出 $q$ 次询问。每次询问给出一个方格 $(x,y)$：

• 如果这个方格是海水，输出 $0$；
• 如果这个方格是陆地，输出它所在岛屿的面积。

你需要依次回答所有询问。

---

【输入描述】

第一行输入三个整数 $n,m,q$，分别表示地图的行数、列数和询问次数。

接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，表示地图。字符串中只包含 # 和 .。

接下来 $q$ 行，每行输入两个整数 $x,y$，表示一次询问的方格坐标。

保证：

• $1\le n,m\le 1000$；
• $n\times m\le 200000$；
• $1\le q\le 2\times 10^5$；
• $1\le x\le n$，$1\le y\le m$。

---

【输出描述】

输出 $q$ 行。

对于每次询问，输出一行一个整数，表示答案。

---

【样例 1】

【样例 1 输入】

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

【样例 1 输出】

3
0
3
3
0

【样例 1 解释】

左上角的岛屿包含 $(1,1),(1,2),(2,1)$ 共 $3$ 个陆地方格。

右下角的岛屿包含 $(2,4),(3,3),(3,4)$ 共 $3$ 个陆地方格。

询问到海水方格时，答案为 $0$。

---

【样例 2】

【样例 2 输入】

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

【样例 2 输出】

2
8
8
0
8
2
0
2

【样例 2 解释】

地图中较大的岛屿面积为 $8$，右下角的岛屿面积为 $2$，左侧上方的岛屿面积为 $2$。

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足 $n,m\le 20$ 且 $q\le 100$。

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足地图中所有陆地连成一个连通块。

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例仅满足完整数据范围，无额外限制。

---

【数据规模与约定】

测试点编号	分数	特殊性质
1 ~ 3	15	$n,m\le 20$ 且 $q\le 100$
4 ~ 6	20	地图中所有陆地连成一个连通块
7 ~ 9		每个岛屿面积均不超过 $10$
10 ~ 12		$n\times m\le 50000$
13 ~ 15	25	无额外限制

对于所有测试点，均满足 $1\le n,m\le 1000$，$n\times m\le 200000$，$1\le q\le 2\times 10^5$。

点击下载本题选手目录