#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
vt<ll> mosaic(vt<int> X, vt<int> Y, vt<int> T, vt<int> B, vt<int> L, vt<int> R) {
const int N = size(X), Q = size(T);
if (N <= 5000) {
vt<vt<int>> grid(N+1, vt<int>(N+1));
FOR(i, 1, N) {
grid[1][i] = X[i-1];
grid[i][1] = Y[i-1];
}
vt<vt<int>> psum(N+1, vt<int>(N+1));
FOR(i, 1, N)
FOR(j, 1, N) {
if (i > 1 && j > 1)
grid[i][j] = !grid[i-1][j] & !grid[i][j-1];
psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + grid[i][j];
}
vt<ll> ret(Q);
FOR(i, 0, Q-1)
ret[i] = psum[B[i]+1][R[i]+1] - psum[B[i]+1][L[i]] - psum[T[i]][R[i]+1] + psum[T[i]][L[i]];
return ret;
}
if (*max_element(all(B)) == 0) {
vt<int> psum(N+1);
FOR(i, 0, N-1)
psum[i+1] = psum[i] + X[i];
vt<ll> ret(Q);
FOR(i, 0, Q-1)
ret[i] = psum[R[i]+1] - psum[L[i]];
return ret;
}
if (*max_element(all(X)) == 0 && *max_element(all(Y)) == 0) {
vt<ll> ret(Q);
FOR(i, 0, Q-1) {
L[i] += !L[i];
T[i] += !T[i];
ret[i] = (1ll * (B[i] - T[i] + 1) * (R[i] - L[i] + 1) + (T[i] + L[i] + 1 & 1)) / 2;
}
return ret;
}
vt<vt<int>> queries(N);
FOR(i, 0, Q-1)
queries[T[i]].push_back(i);
const auto transform = [&](const int y, const int n) {
const vt<int> temp(X.begin(), X.begin() + n);
X[0] = Y[y];
FOR(i, 1, n-1)
X[i] = !X[i-1] & !temp[i];
};
vt<ll> ret(Q);
for (const auto &i : queries[0])
ret[i] = X[L[i]];
if (N == 1)
return ret;
transform(1, N);
for (const auto &i : queries[1])
ret[i] = X[L[i]];
if (N == 2)
return ret;
transform(2, N);
set<int> zeros;
FOR(i, 2, N-2)
if (X[i] == X[i+1]) {
assert(!X[i]);
zeros.insert(i);
}
FOR(i, 2, N-1) {
if (X[0] == X[1])
zeros.insert(-i + 2);
else if (X[1] == X[2])
zeros.insert(-i + 3);
for (const auto &j : queries[i]) {
const auto it = zeros.lower_bound(L[j] - i + 3);
if (it == zeros.begin()) {
ret[j] = (X[0] ^ L[j]) & 1;
} else {
const int k = *prev(it) + i - 2;
ret[j] = (max(k+1, L[j]) - k - 1) & 1;
}
}
if (X[0] == X[1])
zeros.erase(zeros.find(-i + 2));
else if (X[1] == X[2])
zeros.erase(zeros.find(-i + 3));
if (i == N-1)
break;
transform(i+1, 4);
if (X[2] == X[3])
zeros.insert(-i + 3);
}
return ret;
}
