#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll tab[N][5], sum[N][5];
ll ar[N], rev[N];
bool F(int a, int b)
{
return !(a | b);
}
void DoBas(int n)
{
int r = min(3, n);
for(int j = 2; j <= r; ++j)
{
tab[n - j + 1][j] = F(tab[n - j + 1][j - 1], tab[n - j + 3][j - 1]);
for(int i = n - j; i >= 1; --i)
tab[i][j] = F(tab[i + 1][j], tab[i][j - 1]);
for(int i = n - j + 2; i <= 2 * (n - j + 1) - 1; ++i)
tab[i][j] = F(tab[i - 1][j], tab[i + 2][j - 1]);
}
for(int j = 1; j <= r; ++j)
for(int i = 1; i <= 2 * (n - j + 1) - 1; ++i)
sum[i][j] = tab[i][j] + sum[i - 1][j];
/*for(int j = 1; j <= 3; ++j)
{
for(int i = 1; i <= 2 * (n - j + 1) - 1; ++i)
cerr << tab[i][j] << " ";
cerr << "\n";
}*/
if(r < 3) return;
for(int i = 1; i <= 2 * n - 5; ++i)
ar[i] = ar[i - 1] + (ll)i * (ll)tab[i][3];
for(int i = 1; i <= 2 * n - 5; ++i)
rev[i] = rev[i - 1] + (ll)(-i) * (ll)tab[i][3];
}
inline ll S(int a, int b, int r)
{
return sum[b][r] - sum[a - 1][r];
}
ll A(int a, int b, int s)
{
ll ans = ar[b] - ar[a - 1];
ans += (ll)(s - a) * (ll)(sum[b][3] - sum[a - 1][3]);
return ans;
}
ll R(int a, int b, int s)
{
ll ans = rev[b] - rev[a - 1];
ans += (ll)(s + b) * (ll)(sum[b][3] - sum[a - 1][3]);
return ans;
}
ll WS(int a, int b, int d)
{
ll ans = A(a, a + d - 2, 1);
ans += R(b - d + 2, b, 1);
ans += (ll)d * (ll)(sum[b - d + 1][3] - sum[a + d - 2][3]);
return ans;
}
ll Query(int n, int i1, int i2, int j1, int j2)
{
ll ans = 0LL;
if(i1 == 1)
{
ans += S(n + j1 - 1, n + j2 - 1, 1);
i1 = 2;
}
//cerr << j1 << " " << j2 << " Xd " << ans << "\n";
if(i1 > i2) return ans;
if(j1 == 1)
{
ans += S(n - i2 + 1, n - i1 + 1, 1);
j1 = 2;
}
//cerr << j1 << " " << j2 << " Xd " << ans << "\n";
if(j1 > j2) return ans;
//cerr << "??? " << i2 << "\n";
if(i1 == 2)
{
ans += S(n - 1 + j1 - 2, n - 1 + j2 - 2, 2);
i1 = 3;
}
//cerr << sum[n - 1 + j1 - 2][2] << " " << sum[n - 1 + j2 - 2][2] << "\n";
//cerr << n - 1 + j1 - 2 << " " << n - 1 + j2 - 2 << " Xd " << ans << "\n";
if(i1 > i2) return ans;
if(j1 == 2)
{
ans += S(n - 1 - i2 + 2, n - 1 - i1 + 2, 2);
j1 = 3;
}
if(j1 > j2) return ans;
//cerr << "First " << ans << " " << i1 << " " << i2 << " " << j1 << " " << j2 << "\n";
int d = i1 - 3, r = (i2 - i1);
j1 -= d; j2 -= d;
ans += WS(n - 2 + j1 - 3 - r, n - 2 + j2 - 3, min(j2 - j1 + 1, i2 - i1 + 1));
return ans;
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R)
{
vector<ll> ans;
int n = X.size(), q = T.size();
for(int i = 1; i <= n; ++i)
tab[i][1] = Y[n - i];
for(int i = n + 1; i <= 2 * n - 1; ++i)
tab[i][1] = X[i - n];
DoBas(n);
for(int i = 0; i < q; ++i)
ans.pb(Query(n, T[i] + 1, B[i] + 1, L[i] + 1, R[i] + 1));
return ans;
}
