#include "mosaic.h"
#define pb push_back
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const long long maxn = 400005;
//pref[maxn][maxn];
long long n;
vector < long long > a[maxn];
vector < long long > arr, state;
map < long long, long long > pos;
vector < long long > pref, suff;
vector < long long > pp, ss;
long long colpref[maxn][3], rowpref[maxn][3];
long long getprefsum(long long l, long long r) /// 1 2 3 4 5
{
if(r < l)return 0;
long long sz = r - l + 1;
long long sum = pp[r] - pp[l-1] - pref[l-1] * sz;
return sum;
}
long long getsuffsum(long long l, long long r)
{
if(r < l)return 0;
long long sz = r - l + 1;
long long sum = ss[l] - ss[r+1] - suff[r+1] * sz;
return sum;
}
long long getsum(long long l, long long r)
{
if(r < l)return 0;
return pref[r] - pref[l-1];
}
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)
{
long long q = (long long)T.size();
std::vector<long long> C(q, 0);
n = X.size();
a[0].resize(n+1, 0);
a[1].resize(n+1, 0);
a[2].resize(n+1, 0);
a[3].resize(n+1, 0);
a[4].resize(n+1, 0);
for (long long j = 5; j <= n; ++ j)
a[j].resize(6, 0);
for (long long i = 1; i <= n; ++ i)
a[1][i] = X[i-1];
for (long long i = 1; i <= n; ++ i)
a[i][1] = Y[i-1];
for (long long i = 2; i <= 3; ++ i)
{
for (long long j = i; j <= n; ++ j)
{
if(!a[i-1][j] && !a[i][j-1])a[i][j] = 1;
else a[i][j] = 0;
}
for (long long j = i; j <= n; ++ j)
{
if(!a[j-1][i] && !a[j][i-1])a[j][i] = 1;
else a[j][i] = 0;
}
}
for (int col = 1; col <= 2; ++ col)
{
for (int i = 1 ; i <= n; ++ i)
colpref[i][col] = colpref[i-1][col] + a[i][col];
}
for (int row = 1; row <= 2; ++ row)
{
for (int i = 1; i <= n; ++ i)
rowpref[i][row] = rowpref[i-1][row] + a[row][i];
}
vector < long long > hor, ver;
arr.pb(0);
state.pb(0);
for (long long i = n; i >= 3; -- i)
{
arr.pb(a[i][3]);
state.pb(i - 3);
}
for (long long j = 4; j <= n; ++ j)
{
arr.pb(a[3][j]);
state.pb(3 - j);
}
arr.pb(0);
state.pb(0);
pref.resize(2*n+2, 0);
suff.resize(2*n+2, 0);
long long sz = arr.size()-1;
for (long long i = 1; i < arr.size()-1; ++ i)
pref[i] = pref[i-1] + arr[i];
for (long long i = arr.size()-2; i >= 1; -- i)
suff[i] = suff[i+1] + arr[i];
pp.resize(2*n+2, 0);
ss.resize(2*n+2, 0);
for (long long i = 1; i < sz; ++ i)
pp[i] = pp[i-1] + pref[i];
for (long long i = sz-1; i >= 1; -- i)
ss[i] = ss[i+1] + suff[i];
for (long long i = 1; i < arr.size()-1; ++ i)
{
//cout << arr[i] << " ";
pos[state[i]] = i;
// cout << state[i] << " " << i << endl;
}
/* cout << endl;
cout << "state " << endl;
for (long long i = 0; i < state.size(); ++ i)
cout << state[i] << " ";
cout << endl;
cout << "hsdiehduie " << endl;
cout << "pos " << endl;
for (long long i = 1; i < arr.size()-1; ++ i)
{
cout << state[i] << "is " << i << endl;
}*/
/* cout << endl;
cout << "****" << endl;
cout << "pref " << endl;
for (auto x: pref)
cout << x << " ";
cout << endl;
for (auto x: pp)
cout << x << " ";
cout << endl;
cout << "****" << endl;
cout << "suff" << endl;
for (auto x: suff)
cout << x << " ";
cout << endl;
for (auto x: ss)
cout << x << " ";
cout << endl;
cout << endl;*/
q = (long long)T.size();
vector < long long > res;
for (long long i = 0; i < q; ++ i)
{
long long t = T[i] + 1;
long long b = B[i] + 1;
long long l = L[i] + 1;
long long r = R[i] + 1;
long long ans = 0;
for (int j = t; j <= min(1LL * 2, b); ++ j)
{
ans += rowpref[r][j] - rowpref[l-1][j];
}
if(t < 3)t = min(1LL * 2, b) + 1;
if(b < t)
{
res.pb(ans);
continue;
}
for (int j = l; j <= min(1LL * 2, r); ++ j)
{
ans += colpref[b][j] - colpref[t-1][j];
}
if(l < 3)l = min(1LL * 2, r) + 1;
if(l > r)
{
res.pb(ans);
continue;
}
long long szh = r - l + 1;
long long szv = b - t + 1;
if(szh > szv)
{
if(szv > 1)
{
long long stateh0 = pos[b - l];
long long stateh1 = pos[b - (l + szv - 2)]; /// rastat
ans += getsuffsum(stateh0, stateh1);
}
long long const0 = pos[b - (l + szv - 1)];
long long const1 = pos[b - r]; /// shte e konst
long long mult = szv;
if(szv > 1)
{
long long up0 = pos[(b-1) - r];
long long up1 = pos[t - r];
ans += getprefsum(up0, up1);
}
ans += getsum(const0, const1) * mult;
res.pb(ans);
}
else
{
if(szh > 1)
{
long long stateh0 = pos[b - l];
long long stateh1 = pos[b - (r-1)]; /// rastat
ans += getsuffsum(stateh0, stateh1);
}
long long const0 = pos[b - r];
long long const1 = pos[(t + szh - 1) - r]; /// shte e konst
long long mult = szh;
if(szh > 1)
{
long long up0 = pos[(t + szh - 2) - r];
long long up1 = pos[t - r];
ans += getprefsum(up0, up1);
}
ans += getsum(const0, const1) * mult;
res.pb(ans);
}
}
// cout << res.size() << endl;
return res;
}
/**
4
1 0 1 0
1 1 0 1
2
0 0 3 3
2 2 3 3
8
0 1 0 1 0 0 1 0
0 1 0 0 1 0 1 0
3
4 4 4 4
2 2 5 5
0 0 1 1
*/
