#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
const int K = 50;
int vert[N][K+2];
int horz[K+2][N];
int prv[N][K+2];
int prh[K+2][N];
int A[2*N];
// N is the middle (N+i, N-i)
vector<long long> mosaic(vector<signed> X, vector<signed> Y, vector<signed> T, vector<signed> B, vector<signed> L, vector<signed> R) {
int n = X.size();
for (int i=0; i<n; i++) horz[1][i+1] = X[i];
for (int i=0; i<n; i++) vert[i+1][1] = Y[i];
for (int i=0; i<min(n, K); i++) horz[i+1][1] = Y[i];
for (int i=0; i<min(n, K); i++) vert[1][i+1] = X[i];
for (int i=2; i<=K+1; i++) {
for (int j=2; j<=n; j++) {
vert[j][i] = !vert[j-1][i] && !vert[j][i-1];
horz[i][j] = !horz[i-1][j] && !horz[i][j-1];
}
}
for (int i=0; i<=n; i++) A[N+i] = horz[K+1][i+1], A[N-i] = vert[i+1][K+1];
for (int i=1; i<=K; i++) {
for (int j=1; j<=n; j++) {
prv[j][i] = prv[j-1][i] + prv[j][i-1] - prv[j-1][i-1] + vert[j][i];
prh[i][j] = prh[i-1][j] + prh[i][j-1] - prh[i-1][j-1] + horz[i][j];
}
}
vector<int> res((int)T.size(), 0);
for (int q=0; q<T.size(); q++) {
int t = T[q]+1; int b=B[q]+1; int l=L[q]+1; int r=R[q]+1;
int pt = min(b, K);
// add t pt l r
res[q] += prh[pt][r] - prh[t-1][r] - prh[pt][l-1] + prh[t-1][l-1];
t = pt+1;
if (t > b) continue;
int pl = min(r, K);
// add t b l pl
res[q] += prv[b][pl] - prv[t-1][pl] - prv[b][l-1] + prv[t-1][l-1];
l = pl + 1;
if (l > r) continue;
int wsz = r - l + 1;
int id1, id2;
// t b l r
int s = min(b, l); b-=s; l-=s;
if (b) id1 = N-b; else id1 = N+l;
s = min(t,r); t-=s; r-=s;
if (t) id2 = N - t; else id2 = N + r;
for (int i=id1; i + wsz - 1 <= id2; i++) {
for (int j=i; j<=i+wsz-1; j++) {
res[q] += A[j];
}
}
}
return res;
}
