#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 4e5+5;
int X[3][MXN], Y[3][MXN];
ll ps[MXN], ps1[MXN], ps2[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++) X[0][i] = X_[i], Y[0][i] = Y_[i];
if(n==1) return vector<ll>(q, X[0][0]);
if(n==2) {
vector<ll> ans(q, 0);
for(int i=0; i<q; i++)
for(int x=T[i]; x<=B[i]; x++)
for(int y=L[i]; y<=R[i]; y++)
ans[i] += (x==1 && y==1 ? !(X[0][1]|Y[0][1]) : (x==0 ? X[0][y] : Y[0][x]));
return ans;
}
X[1][0] = Y[0][1];
X[2][0] = Y[0][2];
Y[1][0] = X[0][1];
Y[2][0] = Y[0][2];
for(int i=1; i<3; i++)
for(int j=1; j<n; j++)
X[i][j] = !(X[i-1][j]|X[i][j-1]),
Y[i][j] = !(Y[i-1][j]|Y[i][j-1]);
for(int i=n-1; i>=2; i--)
ps[2-i+n] += Y[2][i];
for(int j=3; j<n; j++)
ps[j-2+n] += X[2][j];
for(int i=1; i<=2*n-1; i++) {
ps1[i] = ps1[i-1] + i*ps[i];
ps2[i] = ps2[i-1] + (2*n-i)*ps2[i-1];
ps[i] += ps[i-1];
}
for(int i=0; i<3; i++)
for(int j=1; j<n; j++) {
X[i][j] += X[i][j-1];
Y[i][j] += Y[i][j-1];
}
vector<ll> ans(q, 0);
for(int i=0; i<q; i++) {
if(T[i]==0) {
ans[i] += X[0][R[i]] - (L[i]==0 ? 0 : X[0][L[i]-1]);
if(B[i]==0) continue;
T[i]++;
}
if(T[i]==1) {
ans[i] += X[1][R[i]] - (L[i]==0 ? 0 : X[1][L[i]-1]);
if(B[i]==1) continue;
T[i]++;
}
if(L[i]==0) {
ans[i] += Y[0][B[i]] - (T[i]==0 ? 0 : Y[0][T[i]-1]);
if(R[i]==0) continue;
L[i]++;
}
if(L[i]==1) {
ans[i] += X[1][B[i]] - (T[i]==0 ? 0 : Y[1][T[i]-1]);
if(R[i]==1) continue;
L[i]++;
}
int mn = L[i]-B[i], mx = R[i]-T[i], len = max(B[i]-T[i], R[i]-L[i])+1;
ans[i] += ps1[mn+len-2]-ps1[mn-1] - (mn-1)*(ps[mn+len-2]-ps[mn-1])
+ ps2[mx]-ps2[mx-len+1] - (2*n-mx-1)*(ps[mx]-ps[mx-len+1])
+ len*(ps[mx-len+1]-ps[mn+len-2]);
}
return ans;
}
