#include "mosaic.h"
#include <bits/stdc++.h>
#include <vector>
using ll = long long;
using namespace std;
struct seg{
int n;
struct node{
int l; int r; ll sm; ll v;
};
node merge(node a, node b){
if(a.l == -1) return b;
if(a.l > b.l) swap(a, b);
return node{a.l, b.r, a.sm+b.sm, a.v+b.v+b.sm*((ll)(b.l-a.l))};
}
vector<node> t;
seg(vector<int> &a): n(a.size()){
t.resize(2*n);
for(int i = n; i<2*n; i++) t[i] = node{i-n, i-n, a[i-n], a[i-n]};
for(int i = n-1; i>0; i--) t[i] = merge(t[i << 1], t[(i << 1) | 1]);
}
node q(int l, int r){
node left{-1, -1, -1, -1};
node right{-1, -1, -1, -1};
assert(l<=r);
for(l+=n, r+= n; l<=r; l>>=1, r>>=1){
if(l&1) left = merge(left, t[l++]);
if(!(r&1)) right = merge(right, t[r--]);
}
return merge(left, right);
}
};
vector<long long> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r) {
int n = x.size();
int q = t.size();
if(n == 1){
vector<ll> sl(q, x[0]);
return sl;
}
if(n == 2){
vector<vector<int>> mt(2, vector<int>(2));
mt[0] = x;
mt[1][0] = y[1];
mt[1][1] = !(x[1] | y[1]);
vector<ll> sl(n, 0);
for(int j = 0; j<q; j++){
for(int i = t[j]; i<=b[j]; i++){
for(int k = l[j]; k<=r[j]; k++){
sl[j] += mt[i][j];
}
}
}
return sl;
}
vector<int> xx(n-1);
xx[0] = !(x[1] | y[1]);
for(int i = 1; i<n-1; i++) xx[i] = !(xx[i-1] | x[i+1]);
vector<int> yy(n-2);
yy[0] = !(xx[0] | y[2]);
for(int i = 1; i<n-2; i++) yy[i] = !(yy[i-1] | y[i+2]);
vector<int> tr(2*n-5);
tr[n-3] = !(xx[1] | yy[0]);
for(int i = n-2; i<2*n-5; i++) tr[i] = !(tr[i-1] | xx[i-n+4]);
for(int i = n-4; i>=0; i--) tr[i] = !(tr[i+1] | yy[n-3-i]);
vector<ll> px(n, 0);
vector<ll> py(n, 0);
vector<ll> pxx(n, 0);
vector<ll> pyy(n, 0);
px[0] = x[0];
py[0] = y[0];
pxx[0] = y[1]; pxx[1] = pxx[0]+xx[0];
pyy[0] = x[1]; pyy[1] = pyy[0]+xx[0]; pyy[2] = pyy[1]+yy[0];
for(int i = 1; i<n; i++) px[i] = px[i-1]+x[i];
for(int i = 1; i<n; i++) py[i] = py[i-1]+y[i];
for(int i = 2; i<n; i++) pxx[i] = pxx[i-1] +xx[i-1];
for(int i = 3; i<n; i++) pyy[i] = pyy[i-1] + yy[i-2];
seg diag(tr);
reverse(tr.begin(), tr.end());
seg rdiag(tr);
reverse(tr.begin(), tr.end());
vector<ll> sol(q, 0);
for(int i = 0; i<q; i++){
if(t[i] == 0){
sol[i] += px[r[i]]-(l[i] ? px[l[i]-1]: 0);
t[i]++;
}
if(t[i] > b[i]) continue;
if(t[i] == 1){
sol[i] += pxx[r[i]]-(l[i] ? pxx[l[i]-1]: 0);
t[i]++;
}
if(t[i] > b[i]) continue;
if(l[i] == 0){
sol[i] += py[b[i]]-(t[i] ? py[t[i]-1]: 0);
l[i]++;
}
if(l[i] > r[i]) continue;
if(l[i] == 1){
sol[i] += pyy[b[i]]-(t[i] ? pyy[t[i]-1]: 0);
l[i]++;
}
if(l[i] > r[i]) continue;
if(b[i]-t[i] == r[i]- l[i]){
// angolo1 {l, t}
// angolo2 {l, b}
sol[i] += diag.q(l[i]-b[i]+n-3, l[i]-t[i]+n-3).v;
if(b[i]-t[i] > 0) sol[i] += rdiag.q(2*n-6 - (r[i]-t[i]+n-3), 2*n-6 -(l[i]-t[i]+n-2)).v;
}
if(b[i]-t[i] < r[i]-l[i]){
sol[i] += diag.q(l[i]-b[i]+n-3, l[i]-t[i]+n-3).v;
sol[i] += rdiag.q(2*n-6 - (r[i]-t[i]+n-3), 2*n-6 -(r[i]-b[i]+n-3)).v;
if(b[i]-t[i] + 1 <r[i]-l[i]){
ll tmp = diag.q(l[i]-t[i]+n-2, r[i]-b[i]+n-4).sm;
tmp *= (t[i]-b[i]+1);
sol[i] += tmp;
}
}
if(r[i]-l[i] < b[i]-t[i]){
sol[i] += diag.q(l[i]-b[i]+n-3, r[i]-b[i]+n-3).v;
sol[i] += rdiag.q(2*n-6 - (r[i]-t[i]+n-3), 2*n-6 -(l[i]-t[i]+n-3)).v;
if(r[i]-l[i] + 1 <b[i]-t[i]){
ll tmp = diag.q(r[i]-b[i]+n-2, l[i]-t[i]+n-4).sm;
tmp *= (r[i]-l[i]+1);
sol[i] += tmp;
}
}
}
return sol;
}
