#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
bool BEGIN_ALLOC;
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) FOR(i, 0, r)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
std::vector<long long> mosaic124(std::vector<int> X, std::vector<int> Y,
std::vector<int> T, std::vector<int> B,
std::vector<int> L, std::vector<int> R) {
int N = sz(X), Q = sz(T);
vector<vi> pref(N, vi(N)), a(N, vi(N));
F0R(i, N){
pref[0][i] = a[0][i] = X[i];
pref[i][0] = a[i][0] = Y[i];
}
F0R(i, N){
F0R(j, N){
if(i > 0 && j > 0){
a[i][j] = (a[i - 1][j] == 0 && a[i][j - 1] == 0 ? 1 : 0);
}
pref[i][j] = a[i][j];
if(i > 0) pref[i][j] += pref[i - 1][j];
if(j > 0) pref[i][j] += pref[i][j - 1];
if(i > 0 && j > 0) {
pref[i][j] -= pref[i - 1][j - 1];
}
}
}
auto sumRect = [&](int a, int b, int c, int d){
return pref[c][d] - (b == 0 ? 0 : pref[c][b - 1]) - (a == 0 ? 0 : pref[a - 1][d]) + (a == 0 || b == 0 ? 0 : pref[a - 1][b - 1]);
};
vl ans(Q);
F0R(i, Q){
ans[i] = sumRect(T[i], L[i], B[i], R[i]);
}
return ans;
}
std::vector<long long> mosaic6(std::vector<int> X, std::vector<int> Y,
std::vector<int> T, std::vector<int> B,
std::vector<int> L, std::vector<int> R) {
int N = sz(X), Q = sz(T);
vector<vi> a(N), pref(N);
F0R(i, N){
if(i < 3){
a[i].resize(N);
} else{
a[i].resize(3);
}
if(i == 0) a[i] = X;
a[i][0] = Y[i];
if(i > 0){
FOR(j, 1, sz(a[i])){
a[i][j] = (a[i - 1][j] == 0 && a[i][j - 1] == 0);
}
}
// F0R(j, sz(a[i])){
// pref[i][j] = a[i][j];
// if(i > 0) pref[i][j] += pref[i - 1][j];
// if(j > 0) pref[i][j] += pref[i][j - 1];
// if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1];
// }
}
// cerr << "preprocess ! \n";
auto querySingle = [&](int x, int y){
// cerr << "wtf " << x << ' ' << y << '\n';
if(min(x, y) < 3){
return a[x][y];
}
if(x <= y){
int ret = x - 2;
// cerr << x - ret << ' ' << y - ret << " !\n";
return a[x - ret][y - ret];
} else{
int ret = y - 2;
return a[x - ret][y - ret];
}
};
vl ans(Q);
auto query = [&](int a, int b, int c, int d){
if(a == c && b == d) return querySingle(a, b);
return 0;
};
F0R(i, Q){
ans[i] = query(T[i], L[i], B[i], R[i]);
}
return ans;
}
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
std::vector<int> T, std::vector<int> B,
std::vector<int> L, std::vector<int> R) {
if(sz(X) <= 5000) return mosaic124(X, Y, T, B, L, R);
if(L == R && T == B) return mosaic6(X, Y, T, B, L, R);
int N = sz(X), Q = sz(T);
vector<vi> a(N), pref(N);
F0R(i, N){
if(i < 3){
a[i].resize(N);
pref[i].resize(N);
} else{
a[i].resize(3);
pref[i].resize(3);
}
if(i == 0) a[i] = X;
a[i][0] = Y[i];
if(i > 0){
FOR(j, 1, sz(a[i])){
a[i][j] = (a[i - 1][j] == 0 && a[i][j - 1] == 0);
}
}
F0R(j, sz(a[i])){
pref[i][j] = a[i][j];
if(i > 0) pref[i][j] += pref[i - 1][j];
if(j > 0) pref[i][j] += pref[i][j - 1];
if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1];
}
}
auto querySingle = [&](int x, int y){
// cerr << "wtf " << x << ' ' << y << '\n';
if(min(x, y) < 3){
return a[x][y];
}
if(x <= y){
int ret = x - 2;
// cerr << x - ret << ' ' << y - ret << " !\n";
return a[x - ret][y - ret];
} else{
int ret = y - 2;
return a[x - ret][y - ret];
}
};
vl ans(Q);
vl row2, col2;
FOR(i, 2, N) {
row2.pb(a[2][i]);
col2.pb(a[i][2]);
}
vl sumRow(sz(row2)), sumCol(sz(col2));
vl sumRowMul(sz(row2)), sumColMul(sz(col2));
F0R(i, sz(row2)){
sumRow[i] = (i > 0 ? sumRow[i - 1] : 0) + row2[i];
sumCol[i] = (i > 0 ? sumCol[i - 1] : 0) + col2[i];
sumRowMul[i] = (i > 0 ? sumRowMul[i - 1] : 0) + row2[i] * i;
sumColMul[i] = (i > 0 ? sumColMul[i - 1] : 0) + col2[i] * i;
}
auto sumRev = [&](vl& sum, vl& sumMul, int n){
return (n + 1) * sum[n] - sumMul[n];
};
function<ll(int, int)> solveUpperTriangle = [&](int n, int m){
if(n == m) return sumRev(sumRow, sumRowMul, n);
if(n <= m){
ll ans = sumRev(sumRow, sumRowMul, m);
ans -= solveUpperTriangle(m - n - 1, m - n - 1);
return ans;
} else{
ll ans = sumRev(sumRow, sumRowMul, m);
return ans;
}
};
function<ll(int, int)> solveLowerTriangle = [&](int n, int m){
if(n == m) return sumRev(sumCol, sumColMul, n);
if(n <= m){
return sumRev(sumCol, sumColMul, n);
} else{
ll ans = sumRev(sumCol, sumColMul, n);
ans -= solveLowerTriangle(n - m - 1, n - m - 1);
return ans;
}
};
auto solveRect = [&](int n, int m){
if(n < 0 || m < 0) return 0ll;
if(min(n, m) < 3) return 1LL * pref[n][m];
ll partL = pref[1][m] + pref[n][1] - pref[1][1];
ll partU = solveUpperTriangle(n - 2, m - 2);
ll partD = solveLowerTriangle(n - 2, m - 2);
ll diag = min(n - 1, m - 1) * a[2][2];
return partL + partU + partD - diag;
};
auto query = [&](int a, int b, int c, int d){
ll v1 = solveRect(c, d);
ll v2 = solveRect(a - 1, d);
ll v3 = solveRect(c, b - 1);
ll v4 = solveRect(a - 1, b - 1);
return v1 - v2 - v3 + v4;
};
F0R(i, Q){
ans[i] = query(T[i], L[i], B[i], R[i]);
}
return ans;
}
#ifdef LOCAL
int main(){
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int N;
cin >> N;
vi X(N), Y(N);
F0R(i, N) cin >> X[i];
F0R(i, N) cin >> Y[i];
int Q;
cin >> Q;
vi T(Q), B(Q), L(Q), R(Q);
F0R(i, Q){
cin >> T[i] >> B[i] >> L[i] >> R[i];
}
vl ans = mosaic(X, Y, T, B, L, R);
for(auto x : ans) cout << x << ' ';
return 0;
}
#endif //LOCAl
