不等边三角形区域

题目描述

有一个 $N \times N$ 的网格。从顶部数第 $i$ 行、从左数第 $j$ 列的格子记为 $(i,j)$。

网格的每个格子上最多放一个棋子。

网格的状态由 $N$ 个字符串 $S_i$ 给出:

• 如果 $S_i$ 的第 $j$ 个字符是 O,则 $(i,j)$ 上放有棋子;
• 如果 $S_i$ 的第 $j$ 个字符是 X,则 $(i,j)$ 上没有棋子。

给你一个整数 $M$。使用这个 $M$,我们如下定义:放在 $(s,t)$ 的棋子 $P$ 覆盖格子 $(u,v)$,当且仅当以下所有条件都满足:

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

对 $Q$ 个格子 $(X_i,Y_i)$ 中的每一个,求覆盖该格子的棋子个数。

输入格式

输入按以下格式从标准输入给出:

N M
S_1
S_2
⋮
S_N
Q
X_1 Y_1
X_2 Y_2
⋮
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

数据范围

• $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$