4121: 矩形区域内包含的黑色方格数量
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
# Tile Pattern
## 题目描述
有一个 $10^9$ 乘 $10^9$ 的方格网格。让 $(i,j)$ 表示从上往下数第 $(i+1)$ 行、从左往右数第 $(j+1)$ 列的方格 $(0 \leq i,j < 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}$ $\cdots$ $P_{0,N-1}$
$P_{1,0}$ $P_{1,1}$ $\cdots$ $P_{1,N-1}$
$\vdots$
$P_{N-1,0}$ $P_{N-1,1}$ $\cdots$ $P_{N-1,N-1}$
$query_1$
$query_2$
$\vdots$
$query_Q$
每个查询按以下格式给出：
```
A B C D
```
输出
## 输出格式
按照题目要求输出查询的答案，每个答案占一行。
样例输入 复制
3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5样例输出 复制
4
7提示
## 输入输出样例
### 输入样例1
```
3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5
```
### 输出样例1
```
4
7
```
### 输入样例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 < 10^9$
- $0 \leq B \leq D < 10^9$
- $N, Q, A, B, C, D$ 都是整数。
## 题目来源
ABC331D