#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200'007
int n;
int prR[MAXN][2];
int prK[MAXN][2];
//set<int> st;
int prefD[MAXN];
int imaD[MAXN];
long long prefUp[MAXN];
long long prefDw[MAXN];
long long vzemiUp(int x, int y)
{
long long suma=prefUp[y];
if (x!=0) suma-=prefUp[x-1];
///y trqbva da e 1
long long nrm=prefD[y];
if (x!=0) nrm-=prefD[x-1];
int sg=2*n-y;
int rzl=sg-1;
suma=suma-nrm*rzl;
return suma;
}
long long vzemiDw(int x, int y)
{
long long suma=prefDw[y];
if (x!=0) suma-=prefDw[x-1];
///x trqbva da e 1
long long nrm=prefD[y];
if (x!=0) nrm-=prefD[x-1];
int rzl=x;
suma=suma-nrm*rzl;
return suma;
}
long long vzemi(int x, int y)
{
long long suma=prefD[y];
if (x!=0) suma-=prefD[x-1];
return suma;
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
int Q = (int)T.size();
n=(int)X.size();
if (n==1)
{
vector<long long> C(Q, X[0]);
return C;
}
else if (n==2)
{
int tb[2][2];
tb[0][0]=X[0];
tb[0][1]=X[1];
tb[1][0]=Y[1];
if (X[1]==0 && Y[1]==0) tb[1][1]=1;
else tb[1][1]=0;
vector<long long> C(Q,0);
for (int q=0;q<Q;q++)
{
C[q]=0;
for (int w=T[q];w<=B[q];w++)
{
for (int e=L[q];e<=R[q];e++) C[q]+=tb[w][e];
}
}
return C;
}
vector<int> kk2(n);
kk2[0]=X[1];
for (int q=1;q<n;q++)
{
if (Y[q]==0 && kk2[q-1]==0) kk2[q]=1;
else kk2[q]=0;
if (kk2[q]==1)
{
///na q 1 sme
imaD[q-1+n]=1;
}
}
vector<int> kk3(n);
kk3[0]=X[2];
for (int q=1;q<n;q++)
{
if (kk2[q]==0 && kk3[q-1]==0) kk3[q]=1;
else kk3[q]=0;
if (kk3[q]==1)
{
///na q 2 sme
imaD[q-2+n]=1;
}
}
prK[0][0]=Y[0];
for (int q=1;q<n;q++) prK[q][0]=prK[q-1][0]+Y[q];
prK[0][1]=kk2[0];
for (int q=1;q<n;q++) prK[q][1]=prK[q-1][1]+kk2[q];
vector<int> rr2(n);
rr2[0]=Y[1];
for (int q=1;q<n;q++)
{
if (X[q]==0 && rr2[q-1]==0) rr2[q]=1;
else rr2[q]=0;
if (rr2[q]==1)
{
///na 1 q sme
imaD[1-q+n]=1;
}
}
vector<int> rr3(n);
rr3[0]=Y[2];
for (int q=1;q<n;q++)
{
if (rr2[q]==0 && rr3[q-1]==0) rr3[q]=1;
else rr3[q]=0;
if (rr3[q]==1)
{
///na 2 q sme
imaD[2-q+n]=1;
}
}
prR[0][0]=X[0];
for (int q=1;q<n;q++) prR[q][0]=prR[q-1][0]+X[q];
prR[0][1]=rr2[0];
for (int q=1;q<n;q++) prR[q][1]=prR[q-1][1]+rr2[q];
prefD[0]=imaD[0];
for (int q=1;q<=2*n;q++) prefD[q]=prefD[q-1]+imaD[q];
prefUp[0]=imaD[0]*2*n;
for (int q=1;q<=2*n;q++) prefUp[q]=prefUp[q-1]+1LL*imaD[q]*(2*n-q);
prefDw[0]=imaD[0];
for (int q=1;q<=2*n;q++) prefDw[q]=prefDw[q-1]+1LL*imaD[q]*(q+1);
vector<long long> C(Q, 0);
for (int q=0;q<Q;q++)
{
int r1=T[q];
int r2=B[q];
int k1=L[q];
int k2=R[q];
if (r1<2)
{
if (r1==0)
{
C[q]+=prR[k2][0];
if (k1!=0) C[q]-=prR[k1-1][0];
}
if (r2!=0)
{
C[q]+=prR[k2][1];
if (k1!=0) C[q]-=prR[k1-1][1];
}
}
if (k1<2)
{
if (k1==0)
{
C[q]+=prK[r2][0];
if (r1!=0) C[q]-=prK[r1-1][0];
}
if (k2!=0)
{
C[q]+=prK[r2][1];
if (r1!=0) C[q]-=prK[r1-1][1];
}
}
//cout<<"predi1 e "<<C[q]<<"\n";
if (r1==0 && k1==0) C[q]-=X[0];
if (r1==0 && (1>=k1 && 1<=k2)) C[q]-=X[1];
if ((1>=r1 && 1<=r2) && k1==0) C[q]-=Y[1];
if ((1>=r1 && 1<=r2) && (1>=k1 && 1<=k2)) C[q]-=kk2[1];
if (r2<2 || k2<2) continue;
//cout<<"predi e "<<C[q]<<"\n";
r1=max(r1,2);
k1=max(k1,2);
//cout<<r1<<" "<<r2<<" "<<k1<<" "<<k2<<"\n";
int dr=r2-r1+1;
int dk=k2-k1+1;
if (dr==1 && dk==1)
{
C[q]+=imaD[r1-k1+n];
}
else if (dr<dk)
{
int prv=r1-k1+n;
int psl=r2-k1+n;
C[q]+=vzemiUp(prv,psl);
psl=r1-k2+n;
prv=psl+dr-1;
C[q]+=vzemiDw(psl,prv);
if ((dk-dr)>1)
{
prv=prv+1;
psl=r1-k1+n-1;
C[q]+=1LL*dr*vzemi(prv,psl);
}
}
else
{
int prv=r1-k1+n;
int psl=r1-k2+n;
C[q]+=vzemiDw(psl,prv);
//cout<<psl<<" "<<prv<<" "<<C[q]<<"\n";
if (dr==dk)
{
prv++;
psl=r2-k1+n;
C[q]+=vzemiUp(prv,psl);
//cout<<prv<<" "<<psl<<" e quer "<<C[q]<<"\n";
}
else
{
psl=r2-k1+n;
prv=psl-dk+1;
C[q]+=vzemiUp(prv,psl);
if ((dr-dk)>1)
{
psl=prv-1;
prv=r1-k1+n+1;
C[q]+=1LL*dk*vzemi(prv,psl);
}
}
}
}
return C;
}
