102606: [AtCoder]ABC260 G - Scalene Triangle Area

Problem Statement

We have an $N \times N$ grid. The square at the $i$-th row from the top and $j$-th column from the left in this grid is called $(i,j)$.
Each square of the grid has at most one piece.
The state of the grid is given by $N$ strings $S_i$:

• if the $j$-th character of $S_i$ is O, then $(i,j)$ has a piece on it;
• if the $j$-th character of $S_i$ is X, then $(i,j)$ has no piece on it.

You are given an integer $M$. Using this $M$, we define that a piece $P$ placed at $(s,t)$ covers a square $(u,v)$ if all of the following conditions are satisfied:

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

For each of $Q$ squares $(X_i,Y_i)$, find how many pieces cover the square.

Constraints

• $N$, $M$, $X_i$, $Y_i$, and $Q$ are integers.
• $1 \le N \le 2000$
• $1 \le M \le 2 \times N$
• $S_i$ consists of O and X.
• $1 \le Q \le 2 \times 10^5$
• $1 \le X_i,Y_i \le N$

Input

Input is given from Standard Input in the following format:

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$
$Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$

Output

Print $Q$ lines.
The $i$-th line ( $1 \le i \le Q$ ) should contain the number of pieces that covers $(X_i,Y_i)$ as an integer.

Sample Input 1

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

Sample Output 1

1
1
1
0
0
0

Only Square $(1,1)$ contains a piece, which covers the following # squares:

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

Sample Input 2

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

Sample Output 2

1
6
12
8
25

Sample Input 3

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

Sample Output 3

5
3
9
14
5
3

问题描述

我们有一个$N \times N$的网格。这个网格中从上数第$i$行、从左数第$j$列的正方形称为$(i,j)$。

• 如果$S_i$的第$j$个字符为O，那么$(i,j)$上有一个棋子；
• 如果$S_i$的第$j$个字符为X，那么$(i,j)$上没有棋子。

给你一个整数$M$。使用这个$M$，我们定义一个放在$(s,t)$的棋子覆盖正方形$(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