Atcoder ABC 331 - 瓷砖图案

题目描述

有一个网格，由10^9乘10^9的正方形组成。设（i，j）表示从顶部起第（i+1）行和从左侧起第（j+1）列的正方形（0≤i，j<10^9）。

每个方块都是黑色或白色的。正方形（i，j）的颜色由字符P[i mod N][j mod N]表示，其中B表示黑色，W表示白色。这里，a mod b表示当a除以b时的余数。

Q个询问，每个询问给出ABCD四个数，其中（A，B）为左上角，（C，D）为右下角，并要求您查找矩形区域中黑色方块数。

输入描述

第一行N和Q

接下来N行为一个N×N的由w和b组成的矩阵

在接下来Q行为Q个询问，分别有ABCD组成

数据范围

• 1≤N≤1000
• P[i][j] 为W或者B
• 1≤Q≤2×10^5
• 0≤A≤C<10^9
• 0≤B≤D<10^9
• N,Q,A,B,C,D都是正整数

输出描述

输出Q个答案，每个答案一行

提示

样例1解释：

对于第一个查询，图中以（1,2）为左上角、以（3,4）为右下角的矩形区域被红色边框包围，包含四个黑色方块。

对于第二个查询，以（0,3）为左上角，以（4,5）为右下角的矩形区域，由图中的蓝色边框包围，包含七个黑色方块。