#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define vi vector<int>
const int N=2e5+5;
vector<lol> ans;
int n,Q;
int a0[N],a1[N],b0[N],b1[N];
int a[N<<1];
int s[N<<1];
lol s1[N<<1],s2[N<<1];
lol get0(int l,int r){
    return s[r]-s[l-1];
}
lol get1(int l,int r){
    return (s1[r]-s1[l-1])-get0(l,r)*(l-1);
}
lol get2(int l,int r){
    return (s2[l]-s2[r+1])-get0(l,r)*(n-3+n-2-r);
}
lol work(int r,int c){
    if(r<=0 || c<=0) return 0;
    cout<<r<<' '<<c<<endl;
    if(r<=c)
        return get0(n-3+1,n-3+c-r)*r+get1(n-3-r+2,n-3)+get2(n-3+c-r+1,n-3+c);
    return get0(n-3-(r-c)+1,n-3)*c+get1(n-3-c+1,n-3-(r-c))+get2(n-3+1,n-3+c);
}
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<=3){
        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{
                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;
    }
    a0[0] = b0[0] = Y[0];
    a1[0] = Y[1];
    b1[0] = X[1];
    for(int i=1;i<n;i++){
        a0[i] = X[i];
        a1[i] = !(a1[i-1]|a0[i]);
        b0[i] = Y[i];
        b1[i] = !(b1[i-1]|b0[i]);
    }
    a[n-3+1] = !(a1[2]|b1[2]);
    for(int i=n-3;i>=1;i--){
        a[i] = !(b1[n-3-i+3]|a[i+1]);
    }
    for(int i=n-3+1;i<=n-3+n-2;i++){
        a[i] = !(a[i-1]|a1[i-(n-3)+1]);
    }
    a0[0] = a0[1] = a1[0] = a1[1] = 0;
    for(int i=1;i<=n;i++){
        a0[i]+=a0[i-1]; a1[i]+=a1[i-1];
        b0[i]+=b0[i-1]; b1[i]+=b1[i-1];
    }
    // for(int i=1;i<=n-3+n-2;i++) printf("%d",a[i]); puts("");
    for(int i=1;i<=n-3+n-2;i++)
        s[i] = s[i-1]+a[i];
    for(int i=1;i<=n-3+n-2;i++)
        s1[i] = s1[i-1]+1ll*a[i]*i;
    for(int i=n-3+n-2;i>=1;i--)
        s2[i] = s2[i+1]+1ll*a[i]*(n-3+n-2-i+1);
    for(int i=0;i<Q;i++){
        lol res=0;
        if(U[i]==0) res += a0[R[i]]-(L[i]==0? 0:a0[L[i]-1]);
        if(U[i]<=1) res += a1[R[i]]-(L[i]==0? 0:a1[L[i]-1]);
        if(L[i]==0) res += b0[D[i]]-(U[i]==0? 0:b0[U[i]-1]);
        if(L[i]<=1) res += b1[D[i]]-(U[i]==0? 0:b1[U[i]-1]);
        // cout<<res<<endl;
        res += work(D[i]-1,R[i]-1);
        res -= work(U[i]-2,R[i]-1);
        res -= work(D[i]-1,L[i]-2);
        res += work(U[i]-2,L[i]-2);
        ans.push_back(res);
    }
    return ans;
}