#include "mosaic.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
vector<long long> wow(500001);
vector<long long> wut(500001);
long long pr1[4][200001];
long long pr2[200001][4];
long long calc(long long l, long long r, long long d) {
long long ans = 0;
ans+=wut[l+d-1]-wut[l-1];
ans-=(wow[l+d-1]-wow[l-1])*(l-1);
ans-=wut[r]-wut[r-d];
ans+=(wow[r]-wow[r-d])*(r+1);
ans+=(wow[r-d]-wow[l+d-1])*d;
return ans;
}
std::vector<long long> mosaic(std::vector<int> x, std::vector<int> y,
std::vector<int> t, std::vector<int> B,
std::vector<int> l, std::vector<int> r) {
long long n = x.size();
long long q = t.size();
for(long long i = 0; i < 4; i++) {
for(long long j = 0; j < n+1; j++) {
pr1[i][j] = 0;
pr2[j][i] = 0;
}
}
for(long long i = 1; i <= n; i++) {
pr1[1][i] = x[i-1];
if(i <= 3) {
pr2[1][i] = x[i-1];
}
pr2[i][1] = y[i-1];
if(i <= 3) {
pr1[i][1] = y[i-1];
}
}
for(long long i = 2; i <= 3; i++) {
for(long long j = 2; j <= n; j++) {
if(pr1[i][j-1] == 0 && pr1[i-1][j] == 0) {
pr1[i][j] = 1;
}
if(pr2[j-1][i] == 0 && pr2[j][i-1] == 0) {
pr2[j][i] = 1;
}
}
}
vector<long long> troll(2*n+1);
for(long long i = 3; i <= n; i++) {
troll[3-i+n] = pr1[3][i];
troll[i-3+n] = pr2[i][3];
}
for(long long i = 1; i <= 2*n; i++) {
wow[i] = wow[i-1]+troll[i];
wut[i]+=wut[i-1]+troll[i]*i;
}
for(long long i = 1; i <= 3; i++) {
for(long long j = 1; j <= n; j++) {
pr1[i][j]+=pr1[i-1][j]+pr1[i][j-1]-pr1[i-1][j-1];
pr2[j][i]+=pr2[j-1][i]+pr2[j][i-1]-pr2[j-1][i-1];
}
}
vector<long long> answer(q);
for(long long i = 0; i < q; i++) {
long long a = t[i]+1,b = B[i]+1,c = l[i]+1,d = r[i]+1;
long long ans = 0;
if(a <= 2) {
long long x = min(2LL,b);
ans+=pr1[x][d]-pr1[a-1][d]-pr1[x][c-1]+pr1[a-1][c-1];
a = x+1;
}
if(c <= 2 && a <= b) {
long long x = min(2LL,d);
ans+=pr2[b][x]-pr2[a-1][x]-pr2[b][c-1]+pr2[a-1][c-1];
c = x+1;
}
if(a <= b && c <= d) {
ans+=calc(a-d+n,b-c+n,min(b-a+1,d-c+1));
}
answer[i] = ans;
}
return answer;
}
