#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
const ll N5=2e5;
map<ll,ll> pref0, pref1, pref2, prefr[2], prefc[2];
ll sum0(ll l, ll r){
return pref0[r]-pref0[l-1];
}
ll sum1(ll l, ll r){
return pref1[r]-pref1[l-1]-l*sum0(l,r);
}
ll sum2(ll l, ll r){
return pref2[r]-pref2[l-1]-(N-r-1)*sum0(l,r);
}
ll sumr(ll l, ll r, ll i){
return prefr[i][r]-prefr[i][l-1];
}
ll sumc(ll l, ll r, ll i){
return prefc[i][r]-prefc[i][l-1];
}
ll d(ll i, ll j) {return j-i;}
bool val(bool a, bool b) {return (!a) && (!b);}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
ll n=X.size(), q=T.size();
while(n<3){
X.push_back(0);
Y.push_back(0);
n++;
}
prefr[0][0]=X[0];
prefr[1][0]=Y[1];
for(ll i=1; i<n; i++){
prefr[0][i]=X[i];
prefr[1][i]=val(prefr[1][i-1],prefr[0][i]);
}
prefc[0][0]=Y[0];
prefc[1][0]=X[1];
for(ll i=1; i<n; i++){
prefc[0][i]=Y[i];
prefc[1][i]=val(prefc[1][i-1],prefc[0][i]);
}
pref0[d(2,2)]=val(prefr[1][2],prefc[1][2]);
for(ll i=3; i<n; i++){
pref0[d(2,i)]=val(pref0[d(2,i-1)],prefr[1][i]);
pref0[d(i,2)]=val(pref0[d(i-1,2)],prefc[1][i]);
}
for(auto i:pref0){
pref1[i.first]=(i.first+1)*i.second;
pref2[i.first]=(n-i.first)*i.second;
}
for(ll i=1; i<n; i++){
prefr[0][i]+=prefr[0][i-1];
prefr[1][i]+=prefr[1][i-1];
prefc[0][i]+=prefc[0][i-1];
prefc[1][i]+=prefc[1][i-1];
}
for(ll i=3-n; i<=n-2; i++){
pref0[i]+=pref0[i-1];
pref1[i]+=pref1[i-1];
pref2[i]+=pref2[i-1];
}
vector<ll> ANS;
for(ll Q=0; Q<q; Q++){
ll t=T[Q], b=B[Q], l=L[Q], r=R[Q];
ll ans=0;
if(t==0){
ans+=sumr(l,r,0);
t++;
}
if(t==1){
ans+=sumr(l,r,1);
t++;
}
if(l==0){
ans+=sumc(t,b,0);
l++;
}
if(l==1){
ans+=sumc(t,b,1);
l++;
}
ll x=r-l+1, y=b-t+1, z=min(x,y);
ans+=sum1(d(b,l),d(b-z+2,l))+z*sum0(d(b-z+1,l),d(t,r-z+1))+sum2(d(t,r-z+2),d(t,r));
ANS.push_back(ans);
}
return ANS;
}
