#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> X2, Y2;
vector<int> diag; // X - Y
vector<int> inv;
int color(int a, int b) {
if (a == 0 && b == 0) return 1;
else return 0;
}
vector<long long> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R) {
int N = (int)X.size();
int Q = (int)T.size();
if (N == 1) {
return vector<long long>(Q, X[0]);
}
X2.push_back(Y[1]);
for (int i = 1; i < N; i++) X2.push_back(color(X2.back(), X[i]));
Y2.push_back(X[1]);
for (int i = 1; i < N; i++) Y2.push_back(color(Y2.back(), Y[i]));
if (color(X2[2], Y2[2]) == 1) {
for (int i = 0; i <= 2*N; i++) {
if (abs(i - N) % 2 == 0) diag.push_back(1);
else diag.push_back(0);
}
inv = vector<int>(2*N+1, 0);
int p = 3;
while (p < N) {
if (X[p] == 1) {
if (p+1 < N && X[p+1] == 1) p += 2;
else {
inv[N-(p-1)] = 1;
p += 3;
}
}
else p += 2;
}
p = 3;
while (p < N) {
if (Y[p] == 1) {
if (p+1 < N && Y[p+1] == 1) p += 2;
else {
inv[N+(p-1)] = 1;
p += 3;
}
}
else p += 2;
}
for (int i = N+1; i <= 2*N; i++) inv[i] += inv[i-1];
for (int i = N-1; i >= 0; i--) inv[i] += inv[i+1];
for (int i = 0; i <= 2*N; i++) diag[i] = (diag[i] + inv[i]) % 2;
}
else {
X2.push_back(Y[1]);
for (int i = 1; i < N; i++) X2.push_back(color(X2.back(), X[i]));
Y2.push_back(X[1]);
for (int i = 1; i < N; i++) Y2.push_back(color(Y2.back(), Y[i]));
for (int i = 0; i <= 2*N; i++) {
if (abs(i - N) % 2 == 1) diag.push_back(1);
else diag.push_back(0);
}
inv = vector<int>(2*N+1, 0);
int p = 2;
while (p < N) {
if (X[p] == 1) {
if (p+1 < N && X[p+1] == 1) p += 2;
else {
inv[N-(p-1)] = 1;
p += 3;
}
}
else p += 2;
}
p = 2;
while (p < N) {
if (Y[p] == 1) {
if (p+1 < N && Y[p+1] == 1) p += 2;
else {
inv[N+(p-1)] = 1;
p += 3;
}
}
else p += 2;
}
for (int i = N+1; i <= 2*N; i++) inv[i] += inv[i-1];
for (int i = N-1; i >= 0; i--) inv[i] += inv[i+1];
for (int i = 0; i <= 2*N; i++) diag[i] = (diag[i] + inv[i]) % 2;
}
vector<long long> C(Q, 0);
vector<long long> Xsum(1, 0), X2sum(1, 0), Ysum(1, 0), Y2sum(1, 0), diagsum(1, 0), idiagsum(1, 0);
for (int i = 0; i < N; i++) Xsum.push_back(Xsum.back() + X[i]);
for (int i = 0; i < N; i++) X2sum.push_back(X2sum.back() + X2[i]);
for (int i = 0; i < N; i++) Ysum.push_back(Ysum.back() + Y[i]);
for (int i = 0; i < N; i++) Y2sum.push_back(Y2sum.back() + Y2[i]);
for (int i = 0; i <= N*2; i++) diagsum.push_back(diagsum.back() + diag[i]);
for (int i = 0; i <= N*2; i++) idiagsum.push_back(idiagsum.back() + (long long)i*diag[i]);
for (int i = 0; i < Q; i++) {
if (T[i] == 0) {
C[i] += Xsum[R[i]+1] - Xsum[L[i]];
T[i]++;
}
if (T[i] > B[i]) continue;
if (T[i] == 1) {
C[i] += X2sum[R[i]+1] - X2sum[L[i]];
T[i]++;
}
if (T[i] > B[i]) continue;
if (L[i] == 0) {
C[i] += Ysum[B[i]+1] - Ysum[T[i]];
L[i]++;
}
if (L[i] > R[i]) continue;
if (L[i] == 1) {
C[i] += Y2sum[B[i]+1] - Y2sum[T[i]];
L[i]++;
}
if (L[i] > R[i]) continue;
if (B[i] - T[i] > R[i] - T[i]) {
C[i] += idiagsum[N+T[i]-L[i]] - idiagsum[N+T[i]-R[i]]
- (diagsum[N+T[i]-L[i]] - diagsum[N+T[i]-R[i]]) * (N+T[i]-R[i]-1);
C[i] += (diagsum[N+B[i]-R[i]+1] - diagsum[N+T[i]-L[i]]) * (R[i]-L[i]+1);
C[i] += -(idiagsum[N+B[i]-L[i]+1] - idiagsum[N+B[i]-R[i]+1])
+ (diagsum[N+B[i]-L[i]+1] - diagsum[N+B[i]-R[i]+1]) * (N+B[i]-L[i]+1);
}
else {
C[i] += idiagsum[N+B[i]-R[i]] - idiagsum[N+T[i]-R[i]]
- (diagsum[N+B[i]-R[i]] - diagsum[N+T[i]-R[i]]) * (N+T[i]-R[i]-1);
C[i] += (diagsum[N+T[i]-L[i]+1] - diagsum[N+B[i]-R[i]]) * (B[i]-T[i]+1);
C[i] += -(idiagsum[N+B[i]-L[i]+1] - idiagsum[N+T[i]-L[i]+1])
+ (diagsum[N+B[i]-L[i]+1] - diagsum[N+T[i]-L[i]+1]) * (N+B[i]-L[i]+1);
}
}
return C;
}
