103313: [Atcoder]ABC331 D - Tile Pattern
Description
Score : $450$ points
Problem Statement
There is a grid with $10^9$ by $10^9$ squares. Let $(i, j)$ denote the square at the $(i + 1)$-th row from the top and the $(j + 1)$-th column from the left $(0 \leq i, j \lt 10^9)$. (Note the unusual index assignment.)
Each square is black or white. The color of the square $(i, j)$ is represented by a character $P[i \bmod N][j \bmod N]$, where B means black, and W means white. Here, $a \bmod b$ denotes the remainder when $a$ is divided by $b$.
Answer $Q$ queries.
Each query gives you four integers $A, B, C, D$ and asks you to find the number of black squares contained in the rectangular area with $(A, B)$ as the top-left corner and $(C, D)$ as the bottom-right corner.
Constraints
- $1 \leq N \leq 1000$
- $P[i][j]$ is
WorB. - $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$ are all integers.
Input
The input is given from Standard Input in the following format. Here, $\text{query}_i$ is the $i$-th query to be processed.
$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$
Each query is given in the following format:
$A$ $B$ $C$ $D$
Output
Follow the instructions in the problem statement and print the answers to the queries, separated by newlines.
Sample Input 1
3 2 WWB BBW WBW 1 2 3 4 0 3 4 5
Sample Output 1
4 7
The figure below illustrates the upper left part of the grid.
For the first query, the rectangular area with $(1, 2)$ as the top-left corner and $(3, 4)$ as the bottom-right corner, surrounded by the red frame in the figure, contains four black squares.
For the second query, the rectangular area with $(0, 3)$ as the top-left corner and $(4, 5)$ as the bottom-right corner, surrounded by the blue frame in the figure, contains seven black squares.
Sample Input 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
Sample Output 2
621 167 44 344 500000000000000000
Output
B表示黑色，W表示白色。这里，$a \bmod b$表示$a$除以$b$的余数。
回答$Q$个查询。
每个查询会给你四个整数$A, B, C, D$，并要求你找到矩形区域内的黑色方格数量，该矩形区域的左上角为$(A, B)$，右下角为$(C, D)$。
部分
约束
* $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$都是整数。
输入输出格式
输入
输入从标准输入按以下格式给出。这里，$\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$
```
输出
按照问题描述中的说明，按照换行符分隔，打印查询的答案。
样例
样例输入1
```
3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5
```
样例输出1
```
4
7
```
下图显示了网格的左上部分。
对于第一个查询，左上角为$(1, 2)$，右下角为$(3, 4)$的矩形区域（在图中用红色边框包围）包含4个黑色方格。
对于第二个查询，左上角为$(0, 3)$，右下角为$(4, 5)$的矩形区域（在图中用蓝色边框包围）包含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
```