#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
const int N=2e5+10;
typedef long long ll;

int n,q;
bool ax[N][3],ay[3][N];
int sx[N][3],sy[3][N];
ll ssx[N][3],ssy[3][N];

ll calc(int x,int y) {
    if(!x || !y) return 0;
    ll res=sx[x][1]+sy[1][y]-ax[1][1];
    if(x<=y) {
        res+=1ll*(x+1)*(sx[x][2]-sx[1][2])-(ssx[x][2]-ssx[1][2]);
        res+=1ll*(y+1)*(sy[2][y]-sy[2][y-x+2])-(ssy[2][y]-ssy[2][y-x+2])+1ll*(x-1)*(sy[2][y-x+2]-sy[2][2]);
    }
    else {
        res+=1ll*(y+1)*(sy[2][y]-sy[2][1])-(ssy[2][y]-ssy[2][1]);
        res+=1ll*(x+1)*(sx[x][2]-sx[x-y+2][2])-(ssx[x][2]-ssx[x-y+2][2])+1ll*(y-1)*(sx[x-y+2][2]-sx[2][2]);
    }
    return res;
}

vector<ll> mosaic(vector<int> X,vector<int> Y,vector<int> T,vector<int> B,vector<int> L,vector<int> R) {
    n=X.size(),q=T.size();
    swap(X,Y);
    if(n==1) {
        vector<ll> res;
        res.resize(q,X[0]);
        return res;
    }
    for(int i=1;i<=n;i++) ax[i][1]=X[i-1];
    for(int i=1;i<=n;i++) ay[1][i]=Y[i-1];
    ax[1][2]=ay[1][2],ay[2][1]=ax[2][1];
    for(int i=2;i<=n;i++) ax[i][2]=(!ax[i-1][2]) && (!ax[i][1]),ay[2][i]=(!ay[1][i]) && (!ay[2][i-1]);
    for(int i=1;i<=2;i++) {
        for(int j=1;j<=n;j++) {
            sx[j][i]=sx[j-1][i]+ax[j][i],ssx[j][i]=ssx[j-1][i]+j*ax[j][i];
            sy[i][j]=sy[i][j-1]+ay[i][j],ssy[i][j]=ssy[i][j-1]+j*ay[i][j];
        }
    }
    vector<ll> res;
    for(int i=0;i<q;i++) {
        res.push_back(calc(B[i]+1,R[i]+1)-calc(B[i]+1,L[i])-calc(T[i],R[i]+1)+calc(T[i],L[i]));
    }
    return res;
}