#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define vi vector<int>
vector<lol> ans;
int n,Q;
int a[5005][5005];
vector<lol> mosaic(vi X,vi Y,vi U,vi D,vi L,vi R){
    n = X.size();
    Q = U.size();
    if(n<=5000){
        for(int i=0;i<n;i++) a[0][i]=X[i];
        for(int i=0;i<n;i++) a[i][0]=Y[i];
        for(int i=1;i<n;i++)
            for(int j=1;j<n;j++)
                a[i][j] = !(a[i-1][j]|a[i][j-1]);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                if(i) a[i][j] += a[i-1][j];
                if(j) a[i][j] += a[i][j-1];
                if(i&&j) a[i][j] -= a[i-1][j-1];
            }
    }
    for(int i=1;i<n;i++) X[i]+=X[i-1];
    for(int i=0;i<Q;i++){
        lol res=0;
        if(U[i]==0 && D[i]==0){
            res = X[R[i]];
            if(L[i]) res-=X[L[i]-1];
        }
        else if(n>5000){
            if(L[i]==0) L[i]++;
            if(U[i]==0) U[i]++;
            if(L[i]<=R[i] && U[i]<=D[i]){
                int p = R[i]-L[i]+1;
                int q = D[i]-U[i]+1;
                res = 1ll*p*q/2;
                if(1ll*p*q%2 && (L[i]+U[i])%2==0) res++;
            }
        }
        else{
            res = a[D[i]][R[i]];
            if(U[i]) res -= a[U[i]-1][R[i]];
            if(L[i]) res -= a[D[i]][L[i]-1];
            if(U[i]&&L[i]) res += a[U[i]-1][L[i]-1];
        }
        ans.push_back(res);
        // cerr<<res<<endl;
    }
    return ans;
}