#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define NL "\n"
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define PRINTV(v) for (auto a: v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a: v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
ll get(vvl& table, ll x, ll y) {
if (x >= 2 && y >= 2) return 0;
if (x < 0 || y <= 0) return 0;
if (x >= (ll)table.size() || y >= (ll)table.size()) return 0;
return table[x][y];
}
void propagate(ll x, ll y, vvl& table) {
table[x][y] = !(get(table,x-1,y) || get(table,x,y-1));
}
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) {
ll q = (int)t.size();
ll n = x.size();
if (n <= 200) {
vvl table(n,vl(n));
FOR(i,n) table[i][0] = x[i];
FOR(i,n) table[0][i] = y[i];
FORS(x,1,n) {
FORS(y,1,n) {
table[x][y] = !(table[x-1][y] || table[x][y-1]);
}
}
vl ans(q);
FOR(i,q) {
FORS(x,l[i],r[i]+1) {
FORS(y,t[i],b[i]+1) {
ans[i] += table[x][y];
}
}
}
return ans;
}
vvl table;
FOR(i,n) {
if (i <= 2) table.push_back(vl(n));
else table.push_back(vl(3));
}
FOR(i,n) table[i][0] = x[i];
FOR(i,n) table[0][i] = y[i];
FOR(i,n) propagate(1,i,table);
FOR(i,n) propagate(i,1,table);
FOR(i,n) propagate(i,2,table);
FOR(i,n) propagate(2,i,table);
vl diags(2*n-5);
FORS(i,2,n) {
diags[i-2+n-3] = table[i][2];
}
FORS(i,2,n) {
diags[2-i+n-3] = table[2][i];
}
vl dpsum(2*n-5);
ll sum = 0;
FOR(i,2*n-5) {
sum += diags[i];
dpsum[i] = sum;
}
vl dtsum(2*n-5);
vl drsum(2*n-5);
ll tsum = 0;
ll rsum = 0;
FOR(i,2*n-5) {
tsum += diags[i]*(i+1);
dtsum[i] = tsum;
}
FORR(i,2*n-5) {
rsum += diags[i]*(2*n-5-i);
drsum[i] = rsum;
}
vvl rectsum;
FOR(i,n) {
if (i <= 1) rectsum.push_back(vl(n));
else rectsum.push_back(vl(2));
}
FORR(y,n) {
ll maxx = 2;
if (y <= 1) maxx = n;
FORR(x,maxx) {
rectsum[x][y] = get(rectsum,x+1,y)+get(rectsum,x,y+1)-get(rectsum,x+1,y+1)+table[x][y];
}
}
vl res(q);
FOR(i,q) {
ll ans = 0;
if (t[i] <= 1 || l[i] <= 1) {
ans += rectsum[l[i]][t[i]];
}
if (t[i] <= 1) {
ans -= rectsum[r[i]+1][t[i]];
}
if (l[i] <= 1) {
ans -= rectsum[l[i]][b[i]+1];
}
ll x1 = max(2,l[i]);
ll y1 = max(2,t[i]);
ll x2 = r[i];
ll y2 = b[i];
if (x1 > x2 || x2 > y2) {
res[i] = ans;
continue;
}
ll l = x1-y2 +n-3;
ll r = x2-y1 +n-3;
ll w = min(abs(x2-x1),abs(y2-y1))+1;
if (w > 1) {
ans += dtsum[l+w-2]-l*dpsum[l+w-2];
if (l >= 1) {
ans -= dtsum[l]-l*dpsum[l];
}
ans += drsum[r-(w-2)]-(2*n-5-1-r)*dpsum[r];
if (r < 2*n-5-1) ans -= drsum[r+1];
if (r-(w-1) >= 0) ans += (2*n-5-1-r)*dpsum[r-(w-1)];
}
ans += w*dpsum[r-w];
if (l+w-1 > 0) ans -= w*dpsum[l+w-2];
res[i] = ans;
}
return res;
}
