Score : $450$ points

问题描述

存在一个 $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)$ 为右下角的矩形区域内，包含多少个黑色方格。

以上为通义千问 qwen-max 翻译，仅供参考。

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 W or 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$ 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

update @ 2024/3/10 01:15:35