問題文

$N \\times N$ のグリッドがあり、このグリッドの上から $i$ マス目、左から $j$ マス目を $(i,j)$ と呼びます。
このグリッドの各マスには高々 $1$ 個のコマが置かれています。
グリッドの状態は $N$ 個の文字列 $S_i$ として与えられ、

• $S_i$ の $j$ 文字目が O であるとき $(i,j)$ に $1$ つコマが置かれていること
• $S_i$ の $j$ 文字目が X であるとき $(i,j)$ にコマは置かれていないこと

を表します。

整数 $M$ が与えられます。 この $M$ を使って、 $(s,t)$ に置かれているコマ $P$ について、以下の条件を全て満たすマス $(u,v)$ を $P$ が守っているマスと定義します。

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

$Q$ 個のマス $(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