#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
using ll = long long;
ostream& operator<<(ostream& os, vector <ll> &v) {
for (int i = 0; i < v.size(); ++i) {
os << v[i] << " ";
}
os << "\n";
return os;
}
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();
int q = T.size();
if (n == 1) {
vector <ll> C(q);
for (int i = 0; i < q; ++i) {
C[i] = X[0];
}
return C;
}
vector <ll> X2(n - 1);
vector <ll> Y2(n - 1);
if (X[1] || Y[1]) {
X2[0] = 0;
} else {
X2[0] = 1;
}
for (int i = 0; i < n - 1; ++i) {
if (X[i + 1] || X2[i - 1]) {
X2[i] = 0;
} else {
X2[i] = 1;
}
}
Y2[0] = X2[0];
for (int i = 0; i < n - 1; ++i) {
if (Y[i + 1] || Y2[i - 1]) {
Y2[i] = 0;
} else {
Y2[i] = 1;
}
}
vector <ll> XY;
for (int i = n - 2; i >= 0; --i) {
XY.push_back(Y2[i]);
}
for (int i = 1; i < n - 1; ++i) {
XY.push_back(X2[i]);
}
int mid = XY.size() / 2;
for (int i = mid; i > 0; --i) {
if (XY[i]) continue;
if (XY[i + 1] || XY[i - 1]) continue;
XY[i] = 1;
}
for (int i = mid + 1; i < XY.size() - 1; ++i) {
if (XY[i]) continue;
if (XY[i - 1] || XY[i + 1]) continue;
XY[i] = 1;
}
vector <ll> prefX(n + 1);
vector <ll> prefY(n + 1);
vector <ll> prefX2(n + 1);
vector <ll> prefY2(n + 1);
for (int i = 1; i <= n; ++i) {
prefX[i] = prefX[i - 1] + X[i - 1];
prefY[i] = prefY[i - 1] + Y[i - 1];
}
for (int i = 2; i <= n; ++i) {
prefX2[i] = prefX2[i - 1] + X2[i - 2];
prefY2[i] = prefY2[i - 1] + Y2[i - 2];
}
vector <ll> prefXY;
prefXY.push_back(0);
for (int i = 1; i <= XY.size(); ++i) {
prefXY.push_back(prefXY.back() + XY[i - 1]);
}
vector <ll> pXY(XY.size() + 1);
vector <ll> qXY(XY.size() + 1);
ll val = 0;
for (int i = 1; i <= XY.size(); ++i) {
pXY[i] = pXY[i - 1] + XY[i - 1] * val++;
}
val = 0;
for (int i = XY.size() - 1; i >= 0; --i) {
qXY[i] = qXY[i + 1] + XY[i] * val++;
}
// int A[n][n];
// for (int i = 0; i < n; ++i) {
// A[0][i] = X[i];
// A[i][0] = Y[i];
// }
// for (int i = 1; i < n; ++i) {
// for (int j = 1; j < n; ++j) {
// if (A[i - 1][j] || A[i][j - 1]) {
// A[i][j] = 0;
// } else {
// A[i][j] = 1;
// }
// }
// }
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < n; ++j) {
// cerr << A[i][j] << " ";
// }
// cerr << "\n";
// }
// cerr << X2 << Y2 << "\n";
// cerr << prefX << prefY << prefX2 << prefY2;
// cerr << "\n" << XY << "\n";
// cerr << prefXY << pXY << qXY;
vector <ll> C(q);
for (int i = 0; i < q; ++i) {
if (T[i] == 0) {
C[i] += prefX[R[i] + 1] - prefX[L[i]];
}
if (L[i] == 0) {
C[i] += prefY[B[i] + 1] - prefY[max(T[i], 1)];
}
if (T[i] <= 1 && 1 <= B[i]) {
C[i] += prefX2[R[i] + 1] - prefX2[L[i]];
}
if (L[i] <= 1 && 1 <= R[i]) {
C[i] += prefY2[B[i] + 1] - prefY2[max(T[i], 2)];
}
T[i] = max(T[i], 2);
L[i] = max(L[i], 2);
if (T[i] > B[i] || L[i] > R[i]) continue;
int ind1 = L[i] - B[i] + mid;
int ind3 = R[i] - T[i] + mid + 1;
int h = min(B[i] - T[i], R[i] - L[i]);
C[i] += (pXY[ind1 + h] - pXY[ind1]) - (prefXY[ind1 + h] - prefXY[ind1]) * ll(ind1 - 1);
C[i] += (qXY[ind3 - h] - qXY[ind3]) - (prefXY[ind3] - prefXY[ind3 - h]) * ll(XY.size() - ind3 - 1);
int ind2 = ind1 + h;
C[i] += (prefXY[ind3 - h] - prefXY[ind2]) * ll(h + 1);
}
return C;
}
