#include "mosaic.h"
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template <typename T>
class Array2D {
int H = 0, W = 0;
vector<T> data;
public:
Array2D() = default;
Array2D(int h, int w)
: H(h), W(w), data(h * w) {}
Array2D(int h, int w, T val)
: H(h), W(w), data(h * w, val) {}
T& operator()(int i, int j) {
assert(0 <= i && i < H && 0 <= j && j < W);
return data[i * W + j];
}
const T& operator()(int i, int j) const {
assert(0 <= i && i < H && 0 <= j && j < W);
return data[i * W + j];
}
int height() const { return H; }
int width() const { return W; }
void print() const {
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
cout << (*this)(i, j) << " ";
}
cout << endl;
}
}
void print1() const {
for (int i = 1; i < H; ++i) {
for (int j = 1; j < W; ++j) {
cout << (*this)(i, j) << " ";
}
cout << endl;
}
}
};
template <typename T, typename S = ll>
class PrefixSum1D {
vector<S> dp;
// dp: 1-indexed
S sumDp(int l, int r) const {
return dp[r] - dp[l-1];
}
public:
PrefixSum1D() = default;
PrefixSum1D(const vector<T>& arr) {
build(arr);
}
void build(const vector<T>& arr) {
int n = (int)arr.size();
dp = vector<S>(n + 1, (S)0);
for (int i = 1; i <= n; ++i) {
dp[i] = arr[i-1] + dp[i-1];
}
}
// arr: 0-indexed
S sum(int l, int r) const {
return sumDp(l+1, r+1);
}
// void print() {
// print(dp);
// }
};
template <typename T, typename S = ll>
class PrefixSum2D {
Array2D<S> dp;
// dp: 1-indexed
S sumDp(int a, int b, int c, int d) const {
return dp(c, d) - dp(c, b-1) - dp(a-1, d) + dp(a-1, b-1);
}
public:
PrefixSum2D() = default;
PrefixSum2D(const Array2D<T>& grid) {
build(grid);
}
void build(const Array2D<T>& grid) {
int h = grid.height(), w = grid.width();
dp = Array2D<S>(h + 1, w + 1, (S)0);
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
dp(i, j) = (S)grid(i-1, j-1) + dp(i-1, j) + dp(i, j-1) - dp(i-1, j-1);
}
}
}
// grid: 0-indexed
S sum(int a, int b, int c, int d) const {
return sumDp(a+1, b+1, c+1, d+1);
}
void print() const {
dp.print1();
}
};
struct Input {
vector<int>& X; vector<int>& Y;
vector<int>& T; vector<int>& B;
vector<int>& L; vector<int>& R;
};
namespace Subtask124 {
void fillGrid(Array2D<int>& grid) {
int n = (int)grid.height();
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
grid(i, j) = !grid(i-1, j) && !grid(i, j-1);
}
}
}
vector<ll> solve( 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();
Array2D<int> grid(n, n, 0);
for (int j = 0; j < n; j++) grid(0, j) = X[j];
for (int i = 0; i < n; i++) grid(i, 0) = Y[i];
fillGrid(grid);
PrefixSum2D<int, ll> ps2d(grid);
vector<ll> C(Q, 0LL);
for (int k = 0; k < Q; k++) {
int a = T[k], b = L[k], c = B[k], d = R[k];
C[k] = ps2d.sum(a, b, c, d);
}
return C;
}
inline vector<ll> solve(Input& in) {
return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
}
};
namespace Subtask3 {
bool canApply(vector<int>& T, vector<int>& B) {
int Q = (int)T.size();
for (int k = 0; k < Q; ++k) {
if (T[k] != 0 || B[k] != 0) return false;
}
return true;
}
inline bool canApply(Input& in) { return canApply(in.T, in.B); }
vector<ll> solve( vector<int>& X, vector<int>& Y,
vector<int>& T, vector<int>& B,
vector<int>& L, vector<int>& R)
{
int Q = (int)T.size();
PrefixSum1D<int, ll> ps1d(X);
vector<ll> C(Q, 0LL);
for (int k = 0; k < Q; k++) {
int l = L[k], r = R[k];
C[k] = ps1d.sum(l, r);
}
return C;
}
inline vector<ll> solve(Input& in) {
return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
}
};
namespace Subtask5 {
bool canApply(vector<int>& X, vector<int>& Y) {
int n = (int)X.size();
for (int i = 0; i < n; ++i) {
if (X[i] != 0 || Y[i] != 0) return false;
}
return true;
}
inline bool canApply(Input& in) { return canApply(in.X, in.Y); }
vector<ll> solve( vector<int>& X, vector<int>& Y,
vector<int>& T, vector<int>& B,
vector<int>& L, vector<int>& R)
{
int Q = (int)T.size();
vector<ll> C(Q, 0LL);
for (int k = 0; k < Q; k++) {
int a = T[k], b = L[k], c = B[k], d = R[k];
if (a == 0) a += 1;
if (b == 0) b += 1;
ll area = ((ll)c - a + 1) * (d - b + 1);
C[k] = area / 2;
if (area % 2 == 1 && (a + b) % 2 == 0) C[k] += 1;
}
return C;
}
inline vector<ll> solve(Input& in) {
return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
}
};
namespace Subtask6 {
bool canApply( vector<int>& T, vector<int>& B,
vector<int>& L, vector<int>& R)
{
int Q = (int)T.size();
for (int k = 0; k < Q; ++k) {
if (T[k] != B[k] || L[k] != R[k]) return false;
}
return true;
}
inline bool canApply(Input& in) { return canApply(in.T, in.B, in.L, in.R); }
Array2D<int> makeRows(vector<int>& X, vector<int>& Y) {
int n = X.size();
Array2D<int> rows(3, n);
for (int j = 0; j < n; ++j) rows(0, j) = X[j];
rows(1, 0) = Y[1];
rows(2, 0) = Y[2];
for (int i = 1; i < 3; ++i) {
for (int j = 1; j < n; ++j) {
rows(i, j) = (!rows(i-1, j) && !rows(i, j-1));
}
}
return rows;
}
Array2D<int> makeCols(vector<int>& X, vector<int>& Y) {
int n = X.size();
Array2D<int> cols(n, 3);
for (int i = 0; i < n; ++i) cols(i, 0) = Y[i];
cols(0, 1) = X[1];
cols(0, 2) = X[2];
for (int i = 1; i < n; ++i) {
for (int j = 1; j < 3; ++j) {
cols(i, j) = (!cols(i-1, j) && !cols(i, j-1));
}
}
return cols;
}
vector<ll> solve( vector<int>& X, vector<int>& Y,
vector<int>& T, vector<int>& B,
vector<int>& L, vector<int>& R)
{
int Q = (int)T.size();
auto rows = makeRows(X, Y);
auto cols = makeCols(X, Y);
vector<ll> C(Q, 0LL);
for (int k = 0; k < Q; k++) {
int r = T[k], c = L[k];
if (r <= 2) C[k] = rows(r, c);
else if (c <= 2) C[k] = cols(r, c);
else {
if (r >= c) {
r -= c - 2;
c = 2;
C[k] = cols(r, c);
}
else {
c -= r - 2;
r = 2;
C[k] = rows(r, c);
}
}
}
return C;
}
inline vector<ll> solve(Input& in) {
return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
}
};
vector<ll> 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();
Input in{X, Y, T, B, L, R};
if (n <= 5000)
return Subtask124::solve(in);
else if(Subtask3::canApply(in))
return Subtask3::solve(in);
else if(Subtask5::canApply(in))
return Subtask5::solve(in);
else if(Subtask6::canApply(in))
return Subtask6::solve(in);
vector<ll> C(Q, 0ll);
return C;
}
// ____________________________________________
// vector<ll> 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();
// Array2D<int> rows(3, n), cols(n, 3);
// for (int j = 0; j < n; ++j) rows(0, j) = X[j];
// rows(1, 0) = Y[1];
// rows(2, 0) = Y[2];
// for (int i = 1; i < 3; ++i) {
// for (int j = 1; j < n; ++j) {
// rows(i, j) = (!rows(i-1, j) && !rows(i, j-1));
// }
// }
// for (int i = 0; i < n; ++i) cols(i, 0) = Y[i];
// cols(0, 1) = X[1];
// cols(0, 2) = X[2];
// for (int i = 1; i < n; ++i) {
// for (int j = 1; j < 3; ++j) {
// cols(i, j) = (!cols(i-1, j) && !cols(i, j-1));
// }
// }
// vector<ll> C(Q, 0LL);
// for (int k = 0; k < Q; k++) {
// int r = T[k], c = L[k];
// if (r <= 2) C[k] = rows(r, c);
// else if (c <= 2) C[k] = cols(r, c);
// else {
// if (r >= c) {
// r -= c - 2;
// c = 2;
// C[k] = cols(r, c);
// }
// else {
// c -= r - 2;
// r = 2;
// C[k] = rows(r, c);
// }
// }
// }
// return C;
// }
