#include"mosaic.h"
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;

vector<LL>mosaic(vector<int>X,vector<int>Y,vector<int>L,vector<int>R,vector<int>D,vector<int>U){
    const int n=X.size(),q=L.size();
    vector<LL>ans(q);
    map<pair<int,int>,int>A;
    vector<int>a(n),b(n);
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j){
            if(min(i,j)>3)break;
            if(!i)A[{i,j}]=X[j];
            else if(!j)A[{i,j}]=Y[i];
            else A[{i,j}]=!A[{i-1,j}]&&!A[{i,j-1}];
            if(j>=i)a[j-i]=A[{i,j}];else b[i-j]=A[{i,j}];
        }
    vector<LL>SA(n),SB(n),SSA(n),SSB(n);
    SA[0]=a[0];for(int i=1;i<n;++i)SA[i]=SA[i-1]+a[i];
    SB[0]=b[0];for(int i=1;i<n;++i)SB[i]=SB[i-1]+b[i];
    for(int i=1;i<n;++i)SSA[i]=SSA[i-1]+i*a[i];
    for(int i=1;i<n;++i)SSB[i]=SSB[i-1]+i*b[i];
    vector<vector<tuple<int,int,int>>>Q(n);
    for(int i=0;i<q;++i){
        const int l=L[i],r=R[i],d=D[i],u=U[i];
        Q[r].emplace_back(u,i,1);
        if(d)Q[r].emplace_back(d-1,i,-1);
        if(l)Q[l-1].emplace_back(u,i,-1);
        if(l&&d)Q[l-1].emplace_back(d-1,i,1);
    }
    vector<int>si(n);
    vector<vector<int>>s(3,vector<int>(n));
    for(int i=0;i<n;++i){
        for(int j=0,w=0;j<n;++j){
            if(min(i,j)>2)break;
            w+=A[{i,j}]-(j>=i?a[j-i]:b[i-j]);
            if(i<3)si[j]+=w;
            else s[j][i]+=w;
        }
        for(auto [j,id,op]:Q[i]){
            ans[id]+=op*(si[j]+s[min(j,2)][i]);
            if(i>=j)ans[id]+=op*(SA[j]*(j+1)-SSA[j]+(SB[i]-SB[i-j])*(i+1)-(SSB[i]-SSB[i-j])+SB[i-j]*(j+1));
            else ans[id]+=op*(SB[i]*(i+1)-SSB[i]+(SA[j]-SA[j-i])*(j+1)-(SSA[j]-SSA[j-i])+SA[j-i]*(i+1));
        }
    }
    return ans;
}