#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 4e5+5;
ll ps[MXN], ps2[MXN], ps3[MXN], psx[MXN], psx1[MXN], psy[MXN], rem[MXN];
int a[3][MXN];
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
int n = X.size(), q = L.size();
for(int i=0; i<n; i++) {
a[0][i] = X[i];
if(i<3) a[i][0] = Y[i];
}
psx[1] = X[0];
for(int i=2; i<=n; i++) psx[i] = psx[i-1] + X[i-1];
psy[1] = Y[0];
for(int i=2; i<=n; i++) psy[i] = psy[i-1] + Y[i-1];
if(n>=2) {
for(int i=1; i<n; i++)
a[1][i] = !(a[1][i-1]|a[0][i]);
psx1[1] = a[1][0];
for(int i=2; i<=n; i++) psx1[i] = psx1[i-1] + a[1][i-1];
}
int fir=-1;
if(n>=3) {
for(int i=1; i<n; i++) {
a[2][i] = !(a[2][i-1]|a[1][i]);
if(a[2][i]) {
ps[i-2+n]++;
if(fir==-1) fir = i;
}
}
}
for(int i=3; i<n; i++) {
if(fir!=1) {
if(Y[i]==0) ps[1-i+n]++, fir=0;
else if(fir!=2) ps[2-i+n]++, rem[i]++, fir=1;
}
fir++;
}
for(int i=1; i<n; i++) rem[i] += rem[i-1];
// for(int i=1; i<=2*n-1; i++) {
// cout << ps[i] << ' ';
// }
// cout << '\n';
for(int i=1; i<=2*n-1; i++) {
ps2[i] = ps2[i-1] + ps[i]*i;
ps3[i] = ps3[i-1] + ps[i]*(2*n-i);
ps[i] += ps[i-1];
}
vector<ll> ans(q, 0);
for(int i=0; i<q; i++) {
if(L[i]==0) {
ans[i] += psy[B[i]+1] - psy[T[i]];
if(R[i]==0) continue;
L[i]++;
}
if(T[i]==0) {
ans[i] += psx[R[i]+1] - psx[L[i]];
if(B[i]==0) continue;
T[i]++;
}
if(T[i]==1) {
ans[i] += psx1[R[i]+1] - psx1[L[i]];
if(B[i]==1) continue;
T[i]++;
}
if(L[i]==1) ans[i] -= rem[B[i]] - rem[T[i]-1];
// cout << T[i] << ' ' << B[i] << ' ' << L[i] << ' ' << R[i] << '\n';
int mn = L[i]-B[i]+n, mx = R[i]-T[i]+n, len = min(B[i]-T[i], R[i]-L[i])+1;
// cout << mn << ' ' << mx << ' ' << len << '\n';
// cout << mx-len+1 << ' ' << mn+len-2 << '\n';
// cout << ps[mx-len+1] << ' ' << ps[mn+len-2] << '\n';
ans[i] +=
(ps2[mn+len-2]-ps2[mn-1])-(mn-1)*(ps[mn+len-2]-ps[mn-1])
+ (ps3[mx]-ps3[mx-len+1])-(2*n-1-mx)*(ps[mx]-ps[mx-len+1])
+ len*(ps[mx-len+1]-ps[mn+len-2]);
}
return ans;
}
