#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int N = 4e5+5;
int cnt[N], arcalyk[4][N], tarhun[N][4];
const int M = 5005;
int wow(int a, int b){
return (!(a|b)?1:0);
}
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();
assert(X.front()==Y.front());
bool ok = true;
for (int i = 0; i < n; i++)
ok &= X[i] == 0, ok &= Y[i] == 0;
if (ok){
vector<ll> ans;
for(int i = 0; i < (int)L.size(); ++i){
int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
if (x == 1)
x += 1;
if (y == 1)
y += 1;
ll rec = (xx-x+1)*1LL*(yy-y+1);
if (rec % 2 == 0)
ans.push_back(rec/2);
else{
if ((xx+yy)%2)
ans.push_back(rec/2);
else
ans.push_back(rec/2+1);
}
}
return ans;
}
map<pii, int> mp;
for(int i = 1; i <= n; ++i)
mp[{1, i}] = X[i-1], mp[{i, 1}] = Y[i-1];
for(int i = 2; i <= n; ++i)
for(int j = 2; j <= 3; ++j)
mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
for(int i = 2; i <= 3; ++i)
for(int j = 2; j <= n; ++j)
mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
// int ii = 3;
// for(int jj = 3; jj <= n; ++jj)
// cnt[ii-jj+n] = mp[{ii, jj}];
for (auto [key, value]: mp)
cnt[key.first-key.second+n] = value;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= n; j++)
arcalyk[i][j] = mp[{i,j}] + arcalyk[i][j-1];
for (int j = 1; j <= 3; j++)
for (int i = 1; i <= n; i++)
tarhun[i][j] = mp[{i,j}] + tarhun[i-1][j];
// for (int i = 1; i < n+n; i++)
// cnt[i] += cnt[i-1];
vector<ll> ans;
for(int i = 0; i < (int)L.size(); ++i){
int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
ll res = 0;
while (x <= 3 and x <= xx)
res += arcalyk[x][yy]-arcalyk[x][y-1], x += 1;
if (x <= xx){
while (y <= 3 and y <= yy)
res += tarhun[xx][y]-tarhun[x-1][y], y += 1;
}
if (x <= xx and y <= yy){
int a = x-y+n, b = x-yy+n, k = xx-x+1;
swap(a, b);
// for (int j = 0; j < k; j++){
// for (int h = a; h <= b; h++)
// res += cnt[h];
// a += 1;
// b += 1;
// }
int len = b-a+1;
b += k-1;
for (int j = 0; j < k; j++){
res += cnt[a++]*1LL*(j+1);
if (a <= b)
res += cnt[b--]*1LL*(j+1);
}
res += (b-a+1)*1LL*min(k, len);
}
ans.pb(res);
}
return ans;
}
// l = 1, r = 2, k = 5
// 1 2 3 4 5 6 7 8
// 1 1
// 1 1
// 1 1
// 1 1
// 1 1
// 1 2 2 2 2 1
// int main(){
// int n;
// scanf("%d", &n);
// vector<int> X, Y;
// for(int i = 1; i <= n; ++i){
// int x;
// scanf("%d", &x);
// X.pb(x);
// }
// for(int i = 1; i <= n; ++i){
// int x;
// scanf("%d", &x);
// Y.pb(x);
// }
// int q;
// scanf("%d", &q);
// vector<int> T, B, L, R;
// while(q--){
// int a, b, c, d;
// scanf("%d%d%d%d", &a, &b, &c, &d);
// T.pb(a), B.pb(b), L.pb(c), R.pb(d);
// }
// vector<ll> ans = mosaic(X, Y, T, B, L, R);
// for(ll i : ans)
// printf("%lld ", i);
// puts("");
// return 0;
// }
