#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
#define ll long long
#define vl vector<ll>
#define all(aaa) aaa.begin(), aaa.end()
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vb vector<bool>
#define ed "\n"
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
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){
bool tod0 = true;
ff(i, 0, T.size()){
if(T[i] == B[i] && T[i] == 0){
continue;
}
else{
tod0 = false;
break;
}
}
ll n = X.size();
if(tod0){
//cout << "TOD0" << ed;
vl psum(n);
psum[0] = X[0];
ff(i, 1, n){
psum[i] = psum[i-1]+X[i];
}
vl ans;
ff(i, 0, T.size()){
ll l = 0;
if(L[i]-1 >= 0){
l = psum[L[i]-1];
}
ans.pb(psum[R[i]]-l);
}
return ans;
}
bool inic0 = true;
ff(i, 0, n){
if(X[i] == Y[i] && X[i] == 0){
continue;
}
else{
inic0 = false;
break;
}
}
if(inic0){
//cout << "INIC0" << ed;
vl ans;
ff(i, 0, T.size()){
if(B[i] == 0 || R[i] == 0){
ans.pb(0);
continue;
}
if(T[i] == 0){
T[i]++;
}
if(L[i]==0){
L[i]++;
}
if((R[i]-L[i]+1) % 2 == 0){
ll dist = R[i]-L[i]+1;
ll cant = B[i]-T[i]+1;
dist /= 2;
ans.pb(dist*cant);
}
else{
ll dist = R[i]-L[i];
ll cant = B[i]-T[i]+1;
dist /= 2;
ll base = dist*cant;
if(cant % 2 == 0){
base += cant/2;
}
else if((L[i] % 2) == (T[i] % 2)){
cant++;
base += cant/2;
}
else{
cant--;
base += cant/2;
}
ans.pb(base);
}
}
return ans;
}
bool sub6 = true;
ff(i, 0, T.size()){
if(T[i] == B[i] && L[i] == R[i]){
continue;
}
else{
sub6 = false;
}
}
if(sub6){
vector<vl> hori(3, vl(n)), verti(n, vl(3));
hori[0][0] = Y[0];
hori[1][0] = Y[1];
hori[2][0] = Y[2];
verti[0][0] = X[0];
verti[0][1] = X[1];
verti[0][2] = X[2];
ff(i, 0, 3){
ff(j, 0, n){
if(i == 0){
hori[i][j] = X[j];
continue;
}
if(j == 0){
continue;
}
if(hori[i][j-1] == 0 && hori[i-1][j] == 0){
hori[i][j] = 1;
}
else{
hori[i][j] = 0;
}
}
}
ff(i, 1, n){
ff(j, 0, 3){
if(j == 0){
verti[i][j] = Y[i];
continue;
}
if(verti[i][j-1] == 0 && verti[i-1][j] == 0){
verti[i][j] = 1;
}
else{
verti[i][j] = 0;
}
}
}
/*ff(i, 0, 3){
ff(j, 0, n){
cout << hori[i][j] << " ";
}
cout << ed;
}
cout << ed;
ff(i, 0, n){
ff(j, 0, 3){
cout << verti[i][j] << " ";
}
cout << ed;
}*/
vl ans;
ff(i, 0, T.size()){
//cout << ed;
ll x = L[i], y = T[i];
if(x <= 2){
ans.pb(verti[y][x]);
continue;
}
if(y <= 2){
ans.pb(hori[y][x]);
continue;
}
//cout << "ORI " << y << " " << x << ed;
ll minn = min(-1*(2-x), -1*(2-y));
x -= minn;
y -= minn;
//cout << y << " " << x << ed;
if(x <= 2){
//cout << "V";
ans.pb(verti[y][x]);
continue;
}
if(y <= 2){
ans.pb(hori[y][x]);
continue;
}
}
return ans;
}
if(n <= 5000){
vector<vl> grid(n, vl(n));
ff(j, 0, n){
grid[0][j] = X[j];
}
ff(i, 0, n){
grid[i][0] = Y[i];
}
ff(i, 1, n){
ff(j, 1, n){
if(grid[i][j-1] == 0 && grid[i-1][j] == 0){
//cout << "NO";
grid[i][j] = 1;
}
else{
//cout << "YES";
grid[i][j] = 0;
}
}
}
/*ff(i, 0, n){
ff(j, 0, n){
cout << grid[i][j] << " ";
}
cout << ed;
}
cout << ed << ed;*/
vector<vl> psum(n, vl(n));
ff(i, 0, n){
ff(j, 0, n){
if(j == 0){
psum[i][j] = grid[i][j];
continue;
}
psum[i][j] = psum[i][j-1]+grid[i][j];
}
}
/*ff(i, 0, n){
ff(j, 0, n){
cout << psum[i][j] << " ";
}
cout << ed;
}
cout << ed;*/
ff(j, 0, n){
ff(i, 1, n){
psum[i][j] += psum[i-1][j];
}
}
/*ff(i, 0, n){
ff(j, 0, n){
cout << psum[i][j] << " ";
}
cout << ed;
}
cout << ed;*/
ll q = T.size();
vl ans;
ff(i, 0, q){
ll a = 0;
if(L[i]-1 >= 0 && T[i]-1 >= 0){
a = psum[T[i]-1][L[i]-1];
}
ll b = 0;
if(T[i]-1 >= 0){
b = psum[T[i]-1][R[i]];
}
ll c = 0;
if(L[i]-1 >= 0){
c = psum[B[i]][L[i]-1];
}
ll d = psum[B[i]][R[i]];
//cout << a << " " << b << " " << c << " " << d << ed;
ans.pb(d+a-b-c);
}
return ans;
}
}
/*
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> X(N), Y(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &X[i]));
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &Y[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> T(Q), B(Q), L(Q), R(Q);
for (int k = 0; k < Q; k++)
assert(4 == scanf("%d%d%d%d", &T[k], &B[k], &L[k], &R[k]));
fclose(stdin);
std::vector<long long> C = mosaic(X, Y, T, B, L, R);
int S = (int)C.size();
for (int k = 0; k < S; k++)
printf("%lld\n", C[k]);
fclose(stdout);
return 0;
}
*/
