using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 2");
WillReturn.Add("WWB");
WillReturn.Add("BBW");
WillReturn.Add("WBW");
WillReturn.Add("1 2 3 4");
WillReturn.Add("0 3 4 5");
//4
//7
}
else if (InputPattern == "Input2") {
WillReturn.Add("10 5");
WillReturn.Add("BBBWWWBBBW");
WillReturn.Add("WWWWWBBBWB");
WillReturn.Add("BBBWBBWBBB");
WillReturn.Add("BBBWWBWWWW");
WillReturn.Add("WWWWBWBWBW");
WillReturn.Add("WBBWBWBBBB");
WillReturn.Add("WWBBBWWBWB");
WillReturn.Add("WBWBWWBBBB");
WillReturn.Add("WBWBWBBWWW");
WillReturn.Add("WWWBWWBWWB");
WillReturn.Add("5 21 21 93");
WillReturn.Add("35 35 70 43");
WillReturn.Add("55 72 61 84");
WillReturn.Add("36 33 46 95");
WillReturn.Add("0 0 999999999 999999999");
//621
//167
//44
//344
//500000000000000000
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long mN;
static long UB;
static char[,] mBanArr;
static long[,] mRunSumArr;
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(InputList[0]);
mN = wkArr[0];
UB = mN - 1;
mBanArr = CreateBanArr(InputList.Skip(1).Take((int)mN));
// 2次元累積和を求める
mRunSumArr = new long[UB + 1, UB + 1];
for (long LoopX = 0; LoopX <= UB; LoopX++) {
for (long LoopY = 0; LoopY <= UB; LoopY++) {
if (mBanArr[LoopX, LoopY] == 'B') mRunSumArr[LoopX, LoopY] = 1;
}
}
// 累積和を設定する (横方向)
for (long LoopX = 1; LoopX <= UB; LoopX++) {
for (long LoopY = 0; LoopY <= UB; LoopY++) {
mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX - 1, LoopY];
}
}
// 累積和を設定する (縦方向)
for (long LoopX = 0; LoopX <= UB; LoopX++) {
for (long LoopY = 1; LoopY <= UB; LoopY++) {
mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX, LoopY - 1];
}
}
var InsDeriveGridNumSum = new DeriveGridNumSum(mRunSumArr);
foreach (string EachStr in InputList.Skip(1 + (int)mN)) {
SplitAct(EachStr);
long StaY = wkArr[0];
long StaX = wkArr[1];
long EndY = wkArr[2];
long EndX = wkArr[3];
long CurrSum = InsDeriveGridNumSum.DeriveRectSum(StaX, StaY, EndX, EndY);
Console.WriteLine(CurrSum);
}
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をcharの2次元配列に設定する
////////////////////////////////////////////////////////////////
static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new char[0, 0];
}
int UB_X = StrList[0].Length - 1;
int UB_Y = StrList.Count - 1;
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = StrList[Y][X];
}
}
return WillReturn;
}
}
#region DeriveGridNumSum
// グリッドの矩形の数値和を求めるクラス
internal class DeriveGridNumSum
{
private long[,] mRunSumArr;
private long UB_X;
private long UB_Y;
private long mInitBanWidth;
private long mInitBanHeight;
// コンストラクタ(二次元累積和の配列が引数)
internal DeriveGridNumSum(long[,] pRunSumArr)
{
mRunSumArr = pRunSumArr;
UB_X = pRunSumArr.GetUpperBound(0);
UB_Y = pRunSumArr.GetUpperBound(1);
mInitBanWidth = UB_X + 1;
mInitBanHeight = UB_Y + 1;
}
// (pStaX,pStaY)から(pEndX,pEndY)までの合計を求める
internal long DeriveRectSum(long pStaX, long pStaY, long pEndX, long pEndY)
{
long CurrSum = DeriveSum(pEndX, pEndY);
CurrSum -= DeriveSum(pStaX - 1, pEndY);
CurrSum -= DeriveSum(pEndX, pStaY - 1);
CurrSum += DeriveSum(pStaX - 1, pStaY - 1);
return CurrSum;
}
// (0,0)から(pEndX,pEndY)までの合計を求める
private long DeriveSum(long pEndX, long pEndY)
{
if (pEndX < 0) return 0;
if (pEndY < 0) return 0;
var CntList = new List<long>();
CntList.Add(DeriveSumHelper1(pEndX, pEndY));
CntList.Add(DeriveSumHelper2(pEndX, pEndY));
CntList.Add(DeriveSumHelper3(pEndX, pEndY));
CntList.Add(DeriveSumHelper4(pEndX, pEndY));
return CntList.Sum();
}
// 分割1 完全に含む盤面の分
private long DeriveSumHelper1(long pEndX, long pEndY)
{
long AllWidth = pEndX + 1;
long AllHeight = pEndY + 1;
long Cnt1 = AllWidth / mInitBanWidth;
long Cnt2 = AllHeight / mInitBanHeight;
return mRunSumArr[UB_X, UB_Y] * Cnt1 * Cnt2;
}
// 分割2 上の盤面
private long DeriveSumHelper2(long pEndX, long pEndY)
{
long AllWidth = pEndX + 1;
long AllHeight = pEndY + 1;
if (AllWidth % mInitBanWidth == 0) return 0;
long Cnt = AllHeight / mInitBanHeight;
long XMod = pEndX % mInitBanWidth;
return mRunSumArr[XMod, UB_Y] * Cnt;
}
// 分割3 左の盤面
private long DeriveSumHelper3(long pEndX, long pEndY)
{
long AllWidth = pEndX + 1;
long AllHeight = pEndY + 1;
if (AllHeight % mInitBanHeight == 0) return 0;
long Cnt = AllWidth / mInitBanWidth;
long YMod = pEndY % mInitBanHeight;
return mRunSumArr[UB_X, YMod] * Cnt;
}
// 分割4 右下の盤面
private long DeriveSumHelper4(long pEndX, long pEndY)
{
long AllWidth = pEndX + 1;
long AllHeight = pEndY + 1;
if (AllWidth % mInitBanWidth == 0) return 0;
if (AllHeight % mInitBanHeight == 0) return 0;
long XMod = pEndX % mInitBanWidth;
long YMod = pEndY % mInitBanHeight;
return mRunSumArr[XMod, YMod];
}
}
#endregion