#include "mosaic.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;
int upslope(vi &ps, vi &abc, int l, int r){
return (abc[r + 1] - abc[l]) - l * (ps[r + 1] - ps[l]);
}
int downslope(vi &ps, vi &cba, int l, int r){
return cba[r + 1] - cba[l] - (ps.size() - 1 - r) * (ps[r+1] - ps[l]);
}
int solve(int l, int r, int u, int d, int n, vi &ps, vi &abc, vi &cba){
int st = l - d + n - 3;
int N = r - l + 1;
int M = d - u + 1;
int en = st + N + M - 2;
int len = min(N, M) - 1;
// dout2(st,en);
// out(len);
// vout(ps);
return upslope(ps, abc, st, st + len - 1) + downslope(ps, cba, en - len + 1, en) + (ps[en - len + 1] - ps[st + len]) * (len + 1);
}
std::vector<long long> mosaic(std::vector<signed> X, std::vector<signed> Y,
std::vector<signed> T, std::vector<signed> B,
std::vector<signed> L, std::vector<signed> R) {
int N = X.size();
signed Q = (signed)T.size();
std::vector<long long> ans(Q, 0);
//N <= 5000
if(N <= 5000){
vvi grid(N, vi(N));
f0r(i, N)grid[0][i] = X[i];
f0r(i, N)grid[i][0] = Y[i];
FOR(i, 1, N){
FOR(j, 1, N){
if(grid[i-1][j] == 0 && grid[i][j-1] == 0)grid[i][j] = 1;
else grid[i][j] = 0;
}
}
vvi ps(N + 1, vi(N + 1));
FOR(i, 1, N+1){
FOR(j, 1, N+1){
ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + grid[i-1][j-1];
}
}
f0r(i, Q){
ans[i] = ps[B[i] + 1][R[i] + 1] - ps[B[i] + 1][L[i]] - ps[T[i]][R[i] + 1] + ps[T[i]][L[i]];
}
}
else{
vvi rows(3, vi(N));
f0r(i,N)rows[0][i] = X[i];
rows[1][0] = Y[1];
rows[2][0] = Y[2];
FOR(i, 1, 3){
FOR(j, 1, N){
if(rows[i-1][j] == 0 && rows[i][j-1] == 0)rows[i][j] = 1;
else rows[i][j] = 0;
}
}
vvi psr(4, vi(N+1));
FOR(i, 1, 4){
FOR(j, 1, N+1){
psr[i][j] = psr[i][j-1] + psr[i-1][j] - psr[i-1][j-1] + rows[i-1][j-1];
}
}
vvi cols(N, vi(3));
f0r(i, N)cols[i][0] = Y[i];
cols[0][1] = X[1]; cols[0][2] = X[2];
FOR(i, 1, N){
FOR(j, 1, 3){
if(cols[i-1][j] == 0 && cols[i][j-1] == 0)cols[i][j] = 1;
else cols[i][j] = 0;
}
}
vvi psc(N+1, vi(4));
FOR(i, 1, N+1){
FOR(j, 1, 4){
psc[i][j] = psc[i-1][j] + psc[i][j-1] - psc[i-1][j-1] + cols[i-1][j-1];
}
}
vi v;
for(int i = N-1; i>=2; i--){
v.pb(cols[i][2]);
}
FOR(i, 3, N){
v.pb(rows[2][i]);
}
int M = v.size();
vi ps(M + 1);
FOR(i, 1, M+1){
ps[i] = ps[i-1] + v[i-1];
}
vi abc(M+1);
FOR(i, 1, M+1){
abc[i] = abc[i-1] + v[i-1] * i;
}
vi cba(M+1);
FOR(i, 1, M+1){
cba[i] = cba[i-1] + v[i-1] * (M + 1 - i);
}
f0r(i, Q){
if(B[i] <= 2){
ans[i] = psr[B[i] + 1][R[i] + 1] - psr[B[i] + 1][L[i]] - psr[T[i]][R[i] + 1] + psr[T[i]][L[i]];
}
else if(R[i] <= 2){
ans[i] = psc[B[i] + 1][R[i] + 1] - psc[B[i] + 1][L[i]] - psc[T[i]][R[i] + 1] + psc[T[i]][L[i]];
}
else if(L[i] <= 1 && T[i] <= 1){
int cur;
if(L[i] == 0 && T[i] == 0){
cur = psr[2][R[i] + 1] + psc[B[i] + 1][2] - psr[2][2];
}
else if(L[i] == 1 && T[i] == 1){
int rw = psr[2][R[i] + 1] - psr[1][R[i] + 1] - psr[2][L[i]] + psr[1][1];
int cl = psc[B[i] + 1][2] - psc[B[i] + 1][1] - psc[T[i]][2] + psc[1][1];
cur = rw + cl - rows[1][1];
}
else if(L[i] == 1 && T[i] == 0){
int rw = psr[2][R[i] + 1] - psr[2][1];
int cl = psc[B[i] + 1][2] - psc[B[i] + 1][1];
cur = rw + cl - rows[0][1] - rows[1][1];
}
else{
int rw = psr[2][R[i] + 1] - psr[1][R[i] + 1];
int cl = psc[B[i] + 1][2] - psc[1][2];
cur = rw + cl - rows[1][0] - rows[1][1];
}
// dout(cur);
ans[i] = cur + solve(2, R[i], 2, B[i], N, ps, abc, cba);
}
else if(L[i] <= 1){
int cur = psc[B[i] + 1][2] - psc[T[i]][2] - psc[B[i] + 1][L[i]] + psc[T[i]][L[i]];
ans[i] = cur + solve(2, R[i], T[i], B[i], N, ps, abc, cba);
}
else if(T[i] <= 1){
int cur = psr[2][R[i] + 1] - psr[T[i]][R[i] + 1] - psr[2][L[i]] - psr[T[i]][L[i]];
ans[i] = cur + solve(L[i], R[i], 2, B[i], N, ps, abc, cba);
}
else{
ans[i] = solve(L[i], R[i], T[i], B[i], N, ps, abc, cba);
}
}
}
return ans;
}
