#include <iostream>
#include <vector>
#include "mosaic.h"
#define ll long long
using namespace std;
int r1[200005];
int r2[200005];
int c1[200005];
int c2[200005];
ll r1psum[400005];
ll r2psum[400005];
ll c1psum[400005];
ll c2psum[400005];
ll psum[400005];
ll spsum[400005];
int fin[400005];
int n;
ll getsm(int to, int bo, int le, int ri){
to++;
bo++;
le++;
ri++;
ll sm = 0LL;
if(to==1){
sm += r1psum[ri] - r1psum[le-1];
to++;
if(bo==1){return sm;}
}
if(to==2){
sm += r2psum[ri] - r2psum[le-1];
to++;
if(bo==2){return sm;}
}
if(le==1){
sm += c1psum[bo] - c1psum[to-1];
le++;
if(ri==1){return sm;}
}
if(le==2){
sm += c2psum[bo] - c2psum[to-1];
le++;
if(ri==2){return sm;}
}
int n1 = min(ri-le+1, bo-to+1);
int n2 = max(ri-le+1, bo-to+1);
int st = n + to - ri;
int en = n + bo - le;
sm += spsum[st+n1-2] - spsum[st-1];
sm -= (psum[st+n1-2] - psum[st-1]) * 1LL * (st-1);
sm -= (spsum[en] - spsum[en+1-n1]);
sm += (psum[en] - psum[en+1-n1]) * 1LL * (en+1);
sm += (psum[en+1-n1] - psum[st+n1-2]) * 1LL * n1;
return sm;
}
vector<ll> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r){
n = x.size();
for(int i=0; i<n; i++){
r1[i+1] = x[i];
}
for(int i=0; i<n; i++){
c1[i+1] = y[i];
}
r1psum[0] = 0LL;
for(int i=1; i<=n; i++){
r1psum[i] = r1psum[i-1] + r1[i] * 1LL;
}
c1psum[0] = 0LL;
for(int i=1; i<=n; i++){
c1psum[i] = c1psum[i-1] + c1[i] * 1LL;
}
if(n>1){
r2[1] = c1[2];
c2[1] = r1[2];
}
for(int i=2; i<=n; i++){
r2[i] = (1-r2[i-1]) * (1-r1[i]);
c2[i] = (1-c2[i-1]) * (1-c1[i]);
}
if(n>=2){
r2psum[0] = 0LL;
for(int i=1; i<=n; i++){
r2psum[i] = r2psum[i-1] + r2[i] * 1LL;
}
c2psum[0] = 0LL;
for(int i=1; i<=n; i++){
c2psum[i] = c2psum[i-1] + c2[i] * 1LL;
}
}
if(n>=3){
fin[n] = (1-r2[3]) * (1-c2[3]);
for(int i=n-1; i>=3; i--){
fin[i] = (1-fin[i+1]) * (1-r2[n+3-i]);
}
for(int i=n+1; i<=2*n-3; i++){
fin[i] = (1-fin[i-1]) * (1-c2[i+3-n]);
}
psum[2] = 0LL;
for(int i=3; i<=2*n-3; i++){
psum[i] = psum[i-1] + fin[i] * 1LL;
}
spsum[2] = 0LL;
for(int i=3; i<=2*n-3; i++){
spsum[i] = spsum[i-1] + fin[i] * 1LL * i;
}
}
vector<ll> vec;
int q = t.size();
for(int i=0; i<q; i++){
vec.push_back(getsm(t[i], b[i], l[i], r[i]));
}
return vec;
}
