视线所及之处Ⅱ

题目描述

给定一个由障碍和空地组成的网格，网格共有 H 行、W 列。记第 i 行第 j 列的方格为 (i, j)。
若两个方格位于同一行或同一列，且连接它们的所有方格（包含两端点）中不存在障碍（即均为 .），则称其中一个方格对另一个方格是可见的。

给定 Q 次询问，每次给出一个方格 (X, Y)，保证该方格不含障碍，要求输出从该方格出发在同一行或同一列能看见的方格数量（包含 (X, Y) 自身）。

输入格式

• 第一行包含三个整数：H W Q。
• 接下来 H 行，每行一个长度为 W 的由 . 和 # 组成的字符串 S_i：
  • . 表示空地；
  • # 表示障碍。
• 接下来 Q 行，每行两个整数 X Y，表示一次询问的位置。

输出格式

输出 Q 行，第 i 行输出第 i 次询问的答案。

数据范围与保证

• 1 ≤ H, W ≤ 500
• 1 ≤ Q ≤ 1000000
• 1 ≤ X ≤ H
• 1 ≤ Y ≤ W
• 每个 S_i 的长度为 W
• 每次询问点 (X, Y) 处为 .

样例

输入：

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

输出：

6
2
7