#include "mosaic.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}
int n,m;

struct solver{
    int a[200005];
    ll ssum[200005],sum[200005],qwq[200005];
    void init(){
        rep(i,1,n) sum[i] = sum[i - 1] + a[i];
        rep(i,1,n) ssum[i] = ssum[i - 1] + a[i] * i;
        rep(i,1,n){
            qwq[i] = a[i];
            if(i >= 2) qwq[i] += qwq[i - 2];
        }
    }
    int eval(int x,int y){
        ll answer = 0;
        int p = max(1,x - (2 * y - 1));
        chkmin(p,x + 1);
        
        if(p <= x){
            answer += (x + 2) * (sum[x] - sum[p - 1]) - (ssum[x] - ssum[p - 1]);
            answer -= qwq[x - 1];
            if(p % 2 != x % 2){
                if(p >= 2) answer += qwq[p - 2];
            }else{
                answer += qwq[p - 1];
            }
//            rep(i,p,x) if(a[i] && i % 2 != x % 2) answer--;
            answer /= 2;
        }
        answer += sum[p - 1] * y;
        return answer;
    }
}P[2],Q[2];
vector <int> a[200005],b[200005],c[200005];
ll getsum(int x,int y){
    if(!x || !y) return 0;
//    int up;
    ll answer = b[x][min(y,2)] + c[min(x,2)][y];
/*    rep(i,1,n){
        up = min(n,2);
        if(i <= 2) up = n;
        rep(j,1,up){
            if(i > x || j > y) continue;
            if(!a[i][j]) continue;
            answer++;
        }
    }*/
    rep(p,3,4) if(p <= y) answer += P[p - 3].eval(x,(y - p) / 2 + 1);
    rep(p,3,4) if(p <= x) answer += Q[p - 3].eval(y,(x - p) / 2 + 1);
    rep(p,3,4){
        rep(q,3,4){
            if(p > x || q > y) continue;
            if(!a[p][q]) continue;
            answer -= min((x - p) / 2,(y - q) / 2) + 1;
        }
    }
    return answer;
}

vector<ll> mosaic(vector<int> X, vector<int> Y,vector<int> U, std::vector<int> D,vector<int> L,vector<int> R) {
    n = SZ(X);m = SZ(U);
    rep(i,0,m - 1){
        U[i]++;D[i]++;L[i]++;R[i]++;    
    }
    rep(i,1,max(4,n)){
        if(i <= 4) a[i].resize(n + 1);
        else a[i].resize(5);
    }
    rep(i,1,n){
        a[1][i] = X[i - 1];
        a[i][1] = Y[i - 1];
    }
    rep(i,2,n){
        int up = 4;
        if(i <= 4) up = n;
        rep(j,2,up){
            if(!a[i - 1][j] && !a[i][j - 1]) a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    rep(i,0,n) b[i].resize(3);
    rep(p,0,2) c[p].resize(n + 1);
    rep(i,1,n){
        b[i][1] = a[i][1];
        b[i][2] = a[i][2];
        if(i >= 3){
            c[1][i] = a[1][i];
            c[2][i] = a[2][i];            
        }
    }
//    cerr << "qwq\n";
    rep(i,1,n){
        rep(j,1,2) b[i][j] += b[i][j - 1];
    }
    rep(i,1,n){
        rep(j,1,2) b[i][j] += b[i - 1][j];
    }    
    rep(i,1,2){
        rep(j,1,n) c[i][j] += c[i][j - 1];
    }
    rep(i,1,2){
        rep(j,1,n) c[i][j] += c[i - 1][j];
    }      

    rep(i,3,n){
        P[0].a[i] = a[i][3];
        P[1].a[i] = a[i][4];
        Q[0].a[i] = a[3][i];
        Q[1].a[i] = a[4][i];
    }
    rep(p,0,1){
        P[p].init();
        Q[p].init();
    }

    vector <ll> ans(m);
    rep(i,0,m - 1){
        ans[i] = getsum(D[i],R[i]) - getsum(U[i] - 1,R[i]) - getsum(D[i],L[i] - 1) + getsum(U[i] - 1,L[i] - 1);
    }
    return ans;
}
/*
g++ mosaic.cpp grader2.cpp -o grader.exe -Wall -Wshadow -O2 -std=c++14
*/