瓷砖图案

题目描述

有一个 $10^9 \times 10^9$ 的网格。用 $(i, j)$ 表示从上数第 $(i+1)$ 行、从左数第 $(j+1)$ 列的格子 $(0 \leq 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)$ 为右下角的矩形区域内黑色格子的个数。

输入格式

输入按以下格式从标准输入给出。这里,$\text{query}_i$ 表示要处理的第 $i$ 个询问。

$N$ $Q$
$P[0][0]P[0][1]\dots P[0][N-1]$
$P[1][0]P[1][1]\dots P[1][N-1]$
$\vdots$
$P[N-1][0]P[N-1][1]\dots P[N-1][N-1]$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

每个询问按以下格式给出:

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

输出格式

按照题目要求,用换行分隔输出各询问的答案。

样例

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

4
7

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

对于第一个询问,以 $(1, 2)$ 为左上角、$(3, 4)$ 为右下角的矩形区域(即图中红色框所围部分)包含 $4$ 个黑色格子。

对于第二个询问,以 $(0, 3)$ 为左上角、$(4, 5)$ 为右下角的矩形区域(即图中蓝色框所围部分)包含 $7$ 个黑色格子。

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

621
167
44
344
500000000000000000

数据范围

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