题目描述

有一个 $10^9$ 乘 $10^9$ 的方格网格。让 $(i,j)$ 表示从上往下数第 $(i+1)$ 行、从左往右数第 $(j+1)$ 列的方格 $(0 \le i,j \lt 10^9)$。(注意这种不寻常的索引分配。)

每个方格要么是黑色要么是白色。方格 $(i,j)$ 的颜色由字符 $P[i\ \bmod\ N][j\ \bmod\ N]$表示，其中 B 表示黑色，W 表示白色 这里，$a\ \bmod\ b$ 表示 $a$ 除以 $b$ 的余数。

回答 $Q$ 个查询。

每个查询给出四个整数 $A,B,C,D$，要求你找出以 $(A,B)$ 为左上角、$(C,D)$ 为右下角的矩形区域内包含的黑色方格数量。

输入格式

输入从标准输入中按以下格式给出。这里，$query_i$ 是要处理的第 $i$ 个查询。

N Q
P[0][0]P[0][1]…P[0][N−1]
P[1][0]P[1][1]…P[1][N−1]
⋮
P[N−1][0]P[N−1][1]…P[N−1][N−1]
query1
query2
⋮
queryQ

每个查询按以下格式给出：

$A$ $B$ $C$ $D$

输出格式

按照题目要求输出查询的答案，每个答案占一行。

输入输出样例 #1

输入 #1

3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5

输出 #1

4
7

输入输出样例 #2

输入 #2

10 5
BBBWWWBBBW
WWWWWBBBWB
BBBWBBWBBB
BBBWWBWWWW
WWWWBWBWBW
WBBWBWBBBB
WWBBBWWBWB
WBWBWWBBBB
WBWBWBBWWW
WWWBWWBWWB
5 21 21 93
35 35 70 43
55 72 61 84
36 33 46 95
0 0 999999999 999999999

输出 #2

621
167
44
344
500000000000000000

说明/提示

样例 1 解释

下图展示了网格的左上部分。

对于第一个查询，以 $(1,2)$ 为左上角、$(3,4)$ 为右下角的矩形区域（图中红框所围区域）包含四个黑色方格。

对于第二个查询，以 $(0,3)$ 为左上角、$(4,5)$ 为右下角的矩形区域（图中蓝框所围区域）包含七个黑色方格。

数据范围

• $1\ \leq\ N\ \leq\ 1000$
• $P[i][j]$ 是 W 或 B
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ A\ \leq\ C\ \lt\ 10^9$
• $0\ \leq\ B\ \leq\ D\ \lt\ 10^9$
• $N,\ Q,\ A,\ B,\ C,\ D$ 都是整数