#include "mosaic.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}
int n,q;

vector <int> a[200005];
ll getsum(int x,int y){
    if(!x || !y) return 0;
    int up;
    ll answer = 0;
    rep(i,1,n){
        up = min(n,4);
        if(i <= 4) up = n;
        rep(j,1,up){
            if(i > x || j > y) continue;
            if(!a[i][j]) continue;
            answer++;
            if(i + 2 <= 4 || j + 2 <= 4) continue;
            answer += min((x - i) / 2,(y - j) / 2);
            if((x - i) / 2 && (y - j) / 2) cerr << i << " " << j << endl;
        }
    }
    return answer;
}

vector<ll> mosaic(vector<int> X, vector<int> Y,vector<int> U, std::vector<int> D,vector<int> L,vector<int> R) {
    n = SZ(X);q = SZ(U);
    rep(i,0,q - 1){
        U[i]++;D[i]++;L[i]++;R[i]++;    
    }
    rep(i,1,n){
        if(i <= 4) a[i].resize(n + 1);
        else a[i].resize(5);
    }
    rep(i,1,n){
        a[1][i] = X[i - 1];
        a[i][1] = Y[i - 1];
    }
    rep(i,2,n){
        int up = min(n,4);
        if(i <= 4) up = n;
        rep(j,2,up){
            if(!a[i - 1][j] && !a[i][j - 1]) a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
/*    rep(i,1,n){
        int up = min(n,4);
        if(i <= 4) up = n;
        rep(j,1,up) cerr << a[i][j];
        cerr << endl;
    }*/
    vector <ll> ans(q);
    rep(i,0,q - 1){
        ans[i] = getsum(D[i],R[i]) - getsum(U[i] - 1,R[i]) - getsum(D[i],L[i] - 1) + getsum(U[i] - 1,L[i] - 1);
    }
    return ans;
}
/*
g++ mosaic.cpp grader2.cpp -o grader.exe -Wall -Wshadow -O2 -std=c++14
*/