#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout <<#x << " " << x << endl;
using ll = long long;
const int maxn = 2e5 + 10;
vector<ll> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r ){
int n = x.size(), q = t.size();
if( n <= 5000 ){
vector<vector<ll>> mat(n, vector<ll>(n)), sum(n, vector<ll>(n));
for( int i = 0; i < n; i++ ){
mat[0][i] = x[i], mat[i][0] = y[i];
sum[0][0] = mat[0][0];
if( i > 0 ){
sum[0][i] = sum[0][i - 1] + mat[0][i];
sum[i][0] = sum[i - 1][0] + mat[i][0];
}
}
for( int i = 1; i< n; i++ ) for( int j = 1; j < n; j++ ){
mat[i][j] = (mat[i - 1][j]|mat[i][j - 1])^1;
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i][j];
}
vector<ll> resp(q);
for( int i = 0; i < q; i++ ){
if( t[i] > 0 && l[i] > 0 )
resp[i] = sum[b[i]][r[i]] - sum[t[i] - 1][r[i]] - sum[b[i]][l[i] - 1] + sum[t[i] - 1][l[i] - 1];
else if( t[i] > 0 ){
resp[i] = sum[b[i]][r[i]] - sum[t[i] - 1][r[i]];
}
else if( l[i] > 0 ){
resp[i] = sum[b[i]][r[i]] - sum[b[i]][l[i] - 1];
}
else{
resp[i] = sum[b[i]][r[i]];
}
}
return resp;
}
// construir segunda fila
vector<ll> x2(n), y2(n), sx2(n), sy2(n);
vector<ll> sx(n), sy(n), sum(2*maxn), cont(2*maxn), marcx(n), marcy(n);
sx[0] = sy[0] = x[0];
sx2[0] = x2[0] = y[1];
sy2[0] = y2[0] = x[1];
for( int i = 1; i < n; i++ ){
sx[i] = sx[i - 1] + x[i];
sy[i] = sy[i - 1] + y[i];
x2[i] = (x2[i - 1]|x[i])^1;
y2[i] = (y2[i - 1]|y[i])^1;
sx2[i] = sx2[i - 1] + x2[i];
sy2[i] = sy2[i - 1] + y2[i];
}
if( x2[2] == 0 && y2[2] == 0 ){
marcx[1] = marcy[1] = true;
cont[maxn] = 1;
}
if( x2[3] == 0 && y2[2] == 1 ){
marcx[2] = true;
cont[maxn - 2] = 1;
sum[maxn - 2] = -2;
}
if( x2[2] == 1 && y2[3] == 0 ){
marcy[2] = true;
cont[maxn + 2] = 1;
sum[maxn + 2] = 2;
}
for( int i = 2; i < n; i++ ){
if( i + 1 < n ){
if( x2[i] == 1 && x2[i + 1] == 0 ) sum[maxn - i + 1] = -i + 1, cont[maxn - i + 1] = 1, marcx[i] = true;
else if( i - 2 >= 0 && marcx[i - 2] && x2[i + 1] == 0 ) sum[maxn - i + 1] = -i + 1, cont[maxn - i + 1] = 1, marcx[i] = true;
if( y2[i] == 1 && y2[i + 1] == 0 ) sum[maxn + i - 1] = i - 1, cont[maxn + i - 1] = 1, marcy[i] = true;
else if( i - 2 >= 0 && marcy[i - 2] && y2[i + 1] == 0 ) sum[maxn + i - 1] = i - 1, cont[maxn + i - 1] = 1, marcy[i] = true;
}
}
for( int i = 1; i < (int)sum.size(); i++ ){
sum[i] += sum[i - 1];
cont[i] += cont[i - 1];
}
auto query = [&]( ll l, ll r, ll val, ll t ){
if( l > r ) return 0LL;
return val*(cont[r] - cont[l - 1]) + t*(sum[r] - sum[l - 1]);
};
vector<ll> resp(q);
for( int i = 0; i < q; i++ ){
// bug(i);
if( t[i] == 0 && l[i] == 0 ) resp[i] = x[0];
if( t[i] == 0 ) resp[i] += sx[r[i]] - sx[max(0, l[i] - 1)];
if( l[i] == 0 ) resp[i] += sy[b[i]] - sy[max(0, t[i] - 1)];
// bug(resp[i]);
t[i] = max( t[i], 1 );
l[i] = max( l[i], 1 );
if( t[i] > b[i] || l[i] > r[i] ) continue;
if( t[i] == 1 && l[i] == 1 ) resp[i] += x2[1];
if( t[i] == 1 ) resp[i] += sx2[r[i]] - sx2[max(1, l[i] - 1)];
if( l[i] == 1 ) resp[i] += sy2[b[i]] - sy2[max(1, t[i] - 1)];
// bug(resp[i]);
t[i] = max( t[i], 2 );
l[i] = max( l[i], 2 );
if( t[i] > b[i] || l[i] > r[i] ) continue;
ll L = min(b[i] - r[i], t[i] - l[i]);
ll R = max(b[i] - r[i], t[i] - l[i]);
resp[i] += query( maxn + L, maxn + R, min(b[i] - t[i] + 1, r[i] - l[i] + 1), 0 );
resp[i] += query( maxn + R + 1, maxn + b[i] - l[i], b[i] - l[i] + 1, -1 );
resp[i] += query( maxn + t[i] - r[i], maxn + L - 1, r[i] - t[i] + 1, 1);
}
return resp;
}
