#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef long long ll;
namespace{
const ll mxN=2e5+5;
ll n, q;
ll a[3][mxN];
ll b[mxN][3];
ll pre1[4][mxN], pre2[mxN][4];
ll val[2*mxN];
ll pre[2*mxN], pref[2*mxN], pres[2*mxN];
ll id(ll tar){
return tar+n-3;
}
}
vector<long long> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R) {
memset(pre1, 0, sizeof(pre1));
memset(pre2, 0, sizeof(pre2));
n=X.size();
q=T.size();
for(ll i=0;i<n;i++){
a[0][i]=X[i];
// pre1[0][i]=a[0][i];
}
for(ll i=0;i<3;i++){
a[i][0]=Y[i];
// pre1[i][0]=a[i][0];
}
for(ll i=0;i<n;i++){
b[i][0]=Y[i];
// pre2[i][0]=b[i][0];
}
for(ll i=0;i<3;i++){
b[0][i]=X[i];
// pre2[0][i]=b[0][i];
}
if(n<=2){
for(ll i=1;i<n;i++){
for(ll j=1;j<n;j++){
if(a[i-1][j]==0 && a[i][j-1]==0) a[i][j]=1;
else a[i][j]=0;
}
}
vll ans(q);
for(ll i=0;i<q;i++){
for(ll j=T[i];j<=B[i];j++){
for(ll k=L[i];k<=R[i];k++){
ans[i]+=a[j][k];
}
}
}
return ans;
}
for(ll i=1;i<3;i++){
for(ll j=1;j<n;j++){
if(a[i-1][j]==0 && a[i][j-1]==0) a[i][j]=1;
else a[i][j]=0;
}
}
for(ll i=1;i<n;i++){
for(ll j=1;j<3;j++){
if(b[i-1][j]==0 && b[i][j-1]==0) b[i][j]=1;
else b[i][j]=0;
}
}
for(ll i=0;i<3;i++){
for(ll j=0;j<n;j++){
pre1[i+1][j+1]=pre1[i][j+1]+pre1[i+1][j]-pre1[i][j]+a[i][j];
}
}
for(ll i=0;i<n;i++){
for(ll j=0;j<3;j++){
pre2[i+1][j+1]=pre2[i][j+1]+pre2[i+1][j]-pre2[i][j]+b[i][j];
}
}
for(ll i=n-1;i>=2;i--){
val[id(i-2)]=b[i][2];
}
for(ll i=3;i<n;i++){
val[id(2-i)]=a[2][i];
}
// for(ll i=0;i<=id(n-3);i++){
// cout<<i-n+3<<' '<<val[i]<<'\n';
// }
pre[0]=0;
for(ll i=0;i<=id(n-3);i++){
pre[i+1]=pre[i]+val[i];
}
pref[0]=0;
for(ll i=0;i<=id(n-3);i++){
pref[i+1]=pref[i]+val[i]+pre[i];
// cout<<"pref "<<i-n+3<<' '<<pref[i+1]<<'\n';
}
pres[id(n-3)+2]=0;
for(ll i=id(n-3);i>=0;i--){
pres[i+1]=pres[i+2]+val[i]+pre[id(n-3)+1]-pre[i+1];
}
auto nor=[&](ll tar1, ll tar2){
if(tar1>tar2) return 0LL;
return pre[tar2+1]-pre[tar1];
};
auto ty1=[&](ll tar1, ll tar2){
if(tar2<tar1) return 0LL;
ll re=pref[tar2+1]-pref[tar1]-pre[tar1]*(tar2-tar1+1);
return re;
};
auto ty2=[&](ll tar1, ll tar2){
if(tar2<tar1) return 0LL;
ll re=pres[tar1+1]-pres[tar2+2]-nor(tar2+1, id(n-3))*(tar2-tar1+1);
return re;
};
auto qry=[&](ll x, ll y){
if(x<0) return 0LL;
if(y<0) return 0LL;
if(x<3){
return pre1[x+1][y+1];
}
if(y<3){
return pre2[x+1][y+1];
}
if(x>=y){
// cout<<"x, y "<<x<<' '<<y<<'\n';
ll re=pre1[3][y+1]+pre2[x+1][3]-pre1[3][3];
// cout<<re<<'\n';
re+=nor(id(0), id(x-y))*y;
// cout<<re<<'\n';
re+=ty1(id(x-y+1), id(x-3));
// cout<<re<<'\n';
re+=ty2(id(3-y), id(-1));
// cout<<re<<'\n';
return re;
}
else{
// warning
ll re=pre1[3][y+1]+pre2[x+1][3]-pre1[3][3];
re+=nor(id(x-y), id(0))*x;
re+=ty1(id(1), id(x-3));
re+=ty2(id(3-y), id(x-y-1));
return re;
}
};
// qry(4, 4);
vll ans(q);
for(ll i=0;i<q;i++){
ans[i]=qry(B[i], R[i])-qry(T[i]-1, R[i])-
qry(B[i], L[i]-1)+qry(T[i]-1, L[i]-1);
}
return ans;
}
