#include "mosaic.h"
#include <vector>
#include <iostream>
#include <cassert>
#include <span>
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; }
vector<T> row(int i) const {
assert(0 <= i && i < H);
vector<T> out;
out.reserve(W);
for (int j = 0; j < W; ++j) out.push_back(data[i * W + j]);
return out;
}
vector<T> col(int j) const {
assert(0 <= j && j < W);
vector<T> out;
out.reserve(H);
for (int i = 0; i < H; ++i) out.push_back(data[i * W + j]);
return out;
}
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;
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];
}
}
// dp: 1-indexed
S rangeSumOnDp(int l, int r) const {
return dp[r] - dp[l-1];
}
// arr: 0-indexed
S rangeSum(int l, int r) const {
if (l > r) return 0;
return rangeSumOnDp(l + 1, r + 1);
}
// void print() {
// print(dp);
// }
};
template <typename T, typename S = ll>
class PrefixSum2D {
Array2D<S> dp;
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);
}
}
}
// dp: 1-indexed
S rectSumOnDp(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);
}
// grid: 0-indexed
S rectSum(int a, int b, int c, int d) const {
if (a > c || b > d) return 0;
return rectSumOnDp(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.rectSum(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.rangeSum(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);
}
};
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;
}
template <typename T, typename S = ll>
class PrefixIndexWeightedSum {
vector<S> dp;
PrefixSum1D<T, S> ps;
public:
PrefixIndexWeightedSum() = default;
PrefixIndexWeightedSum(const vector<T>& arr): ps(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] = i * arr[i-1] + dp[i-1];
}
}
// dp: 1-indexed
S weightedSumOnDp(int l, int r) const {
return dp[r] - dp[l-1] - (l-1) * ps.rangeSumOnDp(l, r);
}
// arr: 0-indexed
S weightedSum(int l, int r) const {
if (l > r) return 0;
return weightedSumOnDp(l + 1, r + 1);
}
// void print() {
// print(dp);
// }
};
template <typename T, typename S = ll>
class SuffixIndexWeightedSum {
PrefixIndexWeightedSum<T, S> piws;
int n;
public:
SuffixIndexWeightedSum() = default;
SuffixIndexWeightedSum(const vector<T>& arr) {
n = (int)arr.size();
vector<T> revArr(n);
for (int i = 0; i < n; ++i) revArr[i] = arr[n-1-i];
piws = PrefixIndexWeightedSum<T, S>(revArr);
}
// arr: 0-indexed
S weightedSum(int l, int r) const {
if (l > r) return 0;
return piws.weightedSum(n-1 - r, n-1 - l);
}
};
template <typename T>
class ProjectionGrid {
vector<T> v;
int h, w;
PrefixSum1D<T> ps;
PrefixIndexWeightedSum<T> piws;
SuffixIndexWeightedSum<T> siws;
public:
ProjectionGrid() = default;
ProjectionGrid(span<const int> row0, span<const int> col0)
: h(col0.size()), w(row0.size())
{
v.reserve(h + w - 1);
for (int i = h - 1; i >= 0; --i)
v.push_back(col0[i]);
for (int i = 1; i < w; ++i)
v.push_back(row0[i]);
ps = PrefixSum1D<T>(v);
piws = PrefixIndexWeightedSum<T>(v);
siws = SuffixIndexWeightedSum<T>(v);
}
inline ll rangeSum(int i, int l, int r) {
if (l > r) return 0;
return rangeSumOnVSigned(l - i, r - i);
}
ll wideRectSum(int a, int b, int c, int d) {
return weightedSumOnVSigned(b - c, b - a - 1)
+ (c - a + 1) * rangeSumOnVSigned(b - a, d - c)
+ reverseWeightedSumOnVSigned(d - c + 1, d - a);
}
ll tallRectSum(int a, int b, int c, int d) {
return weightedSumOnVSigned(b - c, d - c - 1)
+ (d - b + 1) * rangeSumOnVSigned(d - c, b - a)
+ reverseWeightedSumOnVSigned(b - a + 1, d - a);
}
inline ll rectSum(int a, int b, int c, int d) {
if (a > c || b > d) return 0;
int h = c - a, w = d - b;
if (w >= h) return wideRectSum(a, b, c, d);
else return tallRectSum(a, b, c, d);
}
private:
// begin rangeSum
inline ll rangeSumOnV(int l, int r) {
if (l > r) return 0;
return ps.rangeSum(l, r);
}
inline ll rangeSumOnVSigned(int l, int r) {
return rangeSumOnV(h-1 + l, h-1 + r);
}
// end rangeSum
// begin weightedSum
inline ll weightedSumOnV(int l, int r) {
return piws.weightedSum(l, r);
}
inline ll weightedSumOnVSigned(int l, int r) {
if (l > r) return 0;
return weightedSumOnV(h-1 + l, h-1 + r);
}
// end weightedSum
// begin reverseWeightedSum
inline ll reverseWeightedSumOnV(int l, int r) {
return siws.weightedSum(l, r);
}
inline ll reverseWeightedSumOnVSigned(int l, int r) {
if (l > r) return 0;
return reverseWeightedSumOnV(h-1 + l, h-1 + r);
}
// end reverseWeightedSum
};
template <typename T>
class OffsetProjectionGrid {
ProjectionGrid<T> pGrid;
int r0, c0;
public:
OffsetProjectionGrid() = default;
OffsetProjectionGrid(span<const int> row0, span<const int> col0, int r0_, int c0_)
: pGrid(row0, col0), r0(r0_), c0(c0_) {}
inline ll rangeSum(int i, int l, int r) {
if (l > r) return 0;
return pGrid.rangeSum(i - r0, l - c0, r - c0);
}
inline ll rectSum(int a, int b, int c, int d) {
if (a > c || b > d) return 0;
return pGrid.rectSum(a - r0, b - c0, c - r0, d - c0);
}
};
namespace Subtask67 {
bool canApply(vector<int>& T, vector<int>& B)
{
int Q = (int)T.size();
for (int k = 0; k < Q; ++k) {
if (T[k] != B[k]) 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();
auto rows = makeRows(X, Y);
auto cols = makeCols(X, Y);
vector<int> row2 = rows.row(2);
vector<int> col2 = cols.col(2);
OffsetProjectionGrid<int> offpGrid( span<int>(row2).subspan(2),
span<int>(col2).subspan(2), 2, 2);
PrefixSum1D<int> rowPs[2];
for (int i = 0; i < 2; ++i) {
rowPs[i] = PrefixSum1D<int>(rows.row(i));
}
vector<ll> C(Q, 0LL);
for (int k = 0; k < Q; k++) {
int i = T[k], l = L[k], r = R[k];
if (i < 2) C[k] = rowPs[i].rangeSum(l, r);
else {
ll &ans = C[k];
int s = max(l, 0);
int e = min(r, 1);
for (int j = s; j <= e; ++j) ans += cols(i, j);
s = max(l, 2);
e = r;
ans += offpGrid.rangeSum(i, s, e);
}
}
return C;
}
inline vector<ll> solve(Input& in) {
return solve(in.X, in.Y, in.T, in.B, in.L, in.R);
}
};
namespace SubtaskAll {
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<int> row2 = rows.row(2);
vector<int> col2 = cols.col(2);
OffsetProjectionGrid<int> offpGrid( span<int>(row2).subspan(2),
span<int>(col2).subspan(2), 2, 2);
PrefixSum1D<int> rowPs[2], colPs[2];
for (int i = 0; i < 2; ++i) {
rowPs[i] = PrefixSum1D<int>(rows.row(i));
colPs[i] = PrefixSum1D<int>(cols.col(i));
}
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];
ll &ans = C[k];
// 1. Top Row Area
int rs = max(a, 0),
re = min(c, 1);
for (int i = rs; i <= re; ++i) ans += rowPs[i].rangeSum(b, d);
// 2. Left Col Area
rs = max(a, 2),
re = c;
int cs = max(b, 0),
ce = min(d, 1);
for (int j = cs; j <= ce; ++j) ans += colPs[j].rangeSum(rs, re);
// 3. Inner Grid Area (by Projection Grid)
a = max(a, 2),
b = max(b, 2);
ans += offpGrid.rectSum(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);
}
};
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();
Input in{X, Y, T, B, L, R};
if (n <= 3)
return Subtask124::solve(in);
else
return SubtaskAll::solve(in);
}
