当前没有测试数据。

G - 等腰三角形的面积

得分：$600$ 分

问题描述

我们有一个 $N \times N$ 的网格。网格中从上往下数第 $i$ 行，从左往右数第 $j$ 列的方块称为 $(i,j)$。
每个方块最多只有一个棋子。

网格的状态由 $N$ 个字符串 $S_i$ 表示:

• 若 $S_i$ 的第 $j$ 个字符是O，则 $(i,j)$ 上有一个棋子；
• 若 $S_i$ 的第 $j$ 个字符是X，则 $(i,j)$ 上没有棋子。

给定一个整数 $M$，我们定义放在 $(s,t)$ 位置的棋子 $P$ 覆盖了方块 $(u,v)$ 如果满足以下所有条件：

• $s \le u \le N$
• $t \le v \le N$
• $(u - s) + \frac{(v - t)}{2} < M$

对于每个方块 $(X_i,Y_i)$，求出有多少个棋子覆盖了该方块。

约束

• $N$, $M$, $X_i$, $Y_i$, 和 $Q$ 都是整数。
• $1 \le N \le 2000$
• $1 \le M \le 2 \times N$
• $S_i$ 由字符 O 和 X 组成。
• $1 \le Q \le 2 \times 10^5$
• $1 \le X_i,Y_i \le N$

---

输入

输入从标准输入中读取，格式如下：

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

$Q$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_Q$ $Y_Q$

输出

输出到标准输出，包含 $Q$ 行。
第 $i$ 行（ $1 \le i \le Q$ ）应包含覆盖了 $(X_i,Y_i)$ 方块的棋子数量，以整数形式表示。

---

4 2
OXXX
XXXX
XXXX
XXXX
6
1 1
1 4
2 2
2 3
3 1
4 4

1
1
1
0
0
0

只有方块 $(1,1)$ 上有一个棋子，覆盖了下面的方块：

``` #### ##.. .... .... ```

---

5 10
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
5
1 1
2 3
3 4
4 2
5 5

1
6
12
8
25

---

8 5
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
6
7 2
8 1
4 5
8 8
3 4
1 7

5
3
9
14
5
3