#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>
const ll MAX = 4e5 + 10;
ll mat[5010][5010];
vector <ll> v;
ll n, m, q;
ll pref[MAX], prefStep[MAX], sufStep[MAX];
ll prefX[MAX], prefY[MAX];
ll pos(ll a, ll b) {
// cout << "pos - " << a << " " << b << "\n";
return n - 2 - (a - b);
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> R, vector<int> R2, vector<int> S, vector<int> S2) {
n = X.size();
for (ll i = 1; i <= n; i++) {
mat[1][i] = X[i - 1];
mat[i][1] = Y[i - 1];
}
for (ll i = 2; i <= n; i++) {
for (ll j = 2; j <= n; j++) {
mat[i][j] = (1 - mat[i - 1][j]) * (1 - mat[i][j - 1]);
}
}
// cout << "mat:\n";
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= n; j++) cout << mat[i][j] << " ";
// cout << "\n";
// }
// cout << "\n";
ll last = X[1];
for (ll i = 1; i < n; i++) {
v.push_back((1 - last) * (1 - Y[i]));
last = v.back();
}
reverse(v.begin(), v.end());
for (ll i = 2; i < n; i++) {
v.push_back((1 - v.back()) * (1 - X[i]));
}
// for (auto e : v) cout << e << " "; cout << "\n";
// cout << pos(R2[1], S[1] + 1) << " " << pos(R[1], S2[1]) << "\n";
prefX[0] = X[0], prefY[0] = Y[0];
for (ll i = 1; i < n; i++) {
prefX[i] = prefX[i - 1] + X[i];
prefY[i] = prefY[i - 1] + Y[i];
}
m = v.size();
pref[0] = v[0], prefStep[0] = v[0], sufStep[m - 1] = v[m - 1];
for (ll i = 1; i < m; i++) {
pref[i] = pref[i - 1] + v[i];
prefStep[i] = prefStep[i - 1] + v[i] * (i + 1);
sufStep[m - i - 1] = sufStep[m - i] + v[m - i - 1] * (i + 1);
}
// cout << "\n";
// cout << "pref - "; for (ll i = 0; i < m; i++) cout << pref[i] << " "; cout << "\n";
// cout << "prefStep - "; for (ll i = 0; i < m; i++) cout << prefStep[i] << " "; cout << "\n";
// cout << "sufStep - "; for (ll i = 0; i < m; i++) cout << sufStep[i] << " "; cout << "\n";
// cout << "\n";
vector <ll> ret;
q = R.size();
for (ll i = 0; i < q; i++) {
ll x = R[i];
ll x2 = R2[i];
ll y = S[i];
ll y2 = S2[i];
ll sol = 0;
if (x == 0) {
sol += prefX[y2] - prefX[y] + X[y];
x++;
}
if (y == 0) {
sol += prefY[x2] - prefY[x] + Y[x];
y++;
}
ll lt = pos(x2, y);
ll rt = pos(x, y2);
ll stepSz = min(x2 - x, y2 - y);
// cout << "query " << i << " -> " << lt << " " << rt << " " << stepSz << "\n";
ll sredina = (pref[rt - stepSz] - pref[lt + stepSz - 1]) * (stepSz + 1);
ll pocetak = (prefStep[lt + stepSz - 1] - prefStep[lt] + v[lt] * (lt + 1)) - lt * (pref[lt + stepSz - 1] - prefStep[lt] + v[lt]);
ll kraj = (sufStep[rt - stepSz + 1] - sufStep[rt] + v[rt] * (m - rt)) - (m - rt - 1) * (pref[rt] - pref[rt - stepSz + 1] + v[rt - stepSz + 1]);
// cout << sredina << " " << pocetak << " " << kraj << "\n";
sol += sredina + pocetak + kraj;
ret.push_back(sol);
}
return ret;
}
