Description

小J是个，他的任务在将炸弹丢到个给定大小为N*N的矩阵中的（s,t)，

这个点会被标记为O

炸弹覆盖范围为：满足以下条件的所有位置（i，j）

s <= i && t <= j

(i - s) + (j - t) / 2 < M

现在小J的上司会给出Q次询问，对于每次询问（x，y）

要求给出对应位置被覆盖了多少次。

Format

Input

第一行给出N,M

接下来N行M列描述地图

接下来一行给出Q

接下来Q行给出询问

N<=2000

M<=2*N

Q<=2e5

Output

见样例

Samples

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

Hint

对于样例1