#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define cmax(a, b) a=max(a, b)
#define cmin(a, b) a=min(a, b)
#define fi first
#define se second
vector<int> diagor, diagol, diago;
int query(int l, int r) {
if (l>r) return 0;
if (l==0) return diago[r];
return diago[r]-diago[l-1];
}
int queryl(int l, int r) {
if (l>r) return 0;
if (l==0) return diagol[r];
int rem=l*query(l, r);
return diagol[r]-diagol[l-1]-rem;
}
int queryr(int l, int r) {
if (l>r) return 0;
if (l==0) return diagor[r];
int rem=(sz(diago)-r-1)*query(l, r);
return diagor[r]-diagor[l-1]-rem;
}
int calc(int x, int y, int a, int b) {
assert(x==0);
int mn=min(a+1, b-y+1);
int l=y-a, midl=y-a+mn-1, midr=b-mn+1, r=b;
int ansl=queryl(l, midl-1);
int ansr=queryr(midr+1, r);
int ansmid=query(midl, midr)*mn;
return ansl+ansr+ansmid;
}
int to_add, sz;
int calcq(int x, int a, int y, int b, vector<vector<int>>& line, vector<vector<int>>& column) {
int ans=0;
int fx=x, fy=y, fa=a, fb=b;
cmax(fx, sz), cmax(fy, sz);
if (fx<=fa && fy<=fb) {
ans+=calc(0, fy-fx+to_add, fa-fx, fb-fx+to_add);
}
if (x<sz && b>=sz) {
for (int i=x; i<min(a+1, sz); i++) {
ans+=line[i][b]-line[i][max(sz-1, y-1)];
}
}
if (y<sz) {
for (int i=y; i<min(b+1, sz); i++) {
ans+=column[a][i]-(x?column[x-1][i]:0);
}
}
return ans;
}
vector<signed> x, y, t, b, l, r;
int n, q;
vector<int> mosaic(vector<signed> X, vector<signed> Y, vector<signed> T, vector<signed> B, vector<signed> L, vector<signed> R) {
x=X, y=Y, t=T, b=B, l=L, r=R, n=sz(x), q=sz(t);
sz=min(5LL, n);
vector<vector<int>> line(sz), column(n);
for (int i=0; i<n; i++) line[0].pb(x[i]), column[i].pb(y[i]);
for (int i=1; i<sz; i++) line[i].pb(column[i][0]), column[0].pb(line[0][i]);
for (int i=1; i<sz; i++) {
for (int j=1; j<n; j++) {
if (line[i-1][j]==0 && line[i][j-1]==0) line[i].pb(1);
else line[i].pb(0);
}
}
for (int i=1; i<n; i++) {
for (int j=1; j<sz; j++) {
if (column[i-1][j]==0 && column[i][j-1]==0) column[i].pb(1);
else column[i].pb(0);
}
}
to_add=n-1-sz+1;
for (int i=n-1; i>=sz; i--) diago.pb(column[i][sz-1]);
for (int i=sz-1; i<n; i++) diago.pb(line[sz-1][i]);
for (int i=0; i<sz; i++) {
for (int j=1; j<n; j++) {
line[i][j]+=line[i][j-1];
column[j][i]+=column[j-1][i];
}
}
diagor=diagol=diago;
diagor[0]=sz(diago)*diago[0];
for (int i=1; i<sz(diago); i++) diagol[i]=diagol[i-1]+diago[i]*(i+1);
for (int i=1; i<sz(diago); i++) diagor[i]=diagor[i-1]+diago[i]*(sz(diago)-i);
for (int i=1; i<sz(diago); i++) diago[i]+=diago[i-1];
vector<int> ans;
for (int tt=0; tt<q; tt++) {
ans.pb(calcq(t[tt], b[tt], l[tt], r[tt], line, column));
}
return ans;
}
