题目描述

我们有一个 $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)$ 的棋子数量。

示例输入 1

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

示例输出 1

1
1
1
0
0
0

只有方格 $(1,1)$ 包含一个棋子，它覆盖了下面的方格 #：

####
##..
....
....

示例输入 2

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

示例输出 2

1
6
12
8
25

示例输入 3

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

示例输出 3

5
3
9
14
5
3