#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);
}
vector<lol> mosaic(vi X,vi Y,vi U,vi D,vi L,vi R){
    n = X.size();
    Q = U.size();
    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;
}