#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;
void propagate(ll x, ll y, map<pl,ll>& table) {
if(table.count({x,y}) > 0) return;
table[{x,y}] = !(table[{x-1,y}] || 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;
}
map<pl,ll> table;
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;
}
priority_queue<pl> todo;
FOR(x,n) {
FOR(y,2) {
todo.push({x,y});
todo.push({y,x});
}
}
map<pl,ll> rectsum;
while (!todo.empty()) {
auto [x,y] = todo.top();
todo.pop();
rectsum[{x,y}] = rectsum[{x+1,y}]+rectsum[{x,y+1}]-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;
}
