/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
縦横 10^9 マスのグリッドがあります。上から i + 1 行目、左から j + 1 列目 (0 \leq i, j \lt 10^9) にあるマスを (i, j) と呼びます。(通常と異なる index の割り当て方に注意してください。)
各マスは黒マスか白マスのいずれかです。マス (i, j) の色は文字 P[i \bmod N][j \bmod N] によって表されて、B ならばマス (i, j) は黒マス、W ならば白マスです。ここで a \bmod b は a を b で割った余りを意味します。
Q 個のクエリが与えられるので順に処理してください。
各クエリでは 4 つの整数 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 番目のクエリについて、(1, 2) を左上隅、(3, 4) を右下隅とする長方形領域は図の赤い枠線に囲まれた部分で、領域に含まれる黒マスの個数は 4 個です。
2 番目のクエリについて、(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
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