#include "mosaic.h"
#define pb push_back
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const long long maxn = 200005;
//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 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;
}
}
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 << 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;
if(t < 3 || l < 3)
{
res.pb(a[t][b]);
continue;
}
long long szh = r - l + 1;
long long szv = b - t + 1;
if(szh >= szv)
{long long ans = 0;
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
{
long long stateh0 = pos[b - l];
long long stateh1 = pos[b - (r-1)]; /// rastat
long long const0 = pos[b - r];
long long const1 = pos[(t + szh) - r]; /// shte e konst
long long mult = szh;
long long up0 = pos[(t + szh - 1) - r];
long long up1 = pos[t - r];
long long ans = 0;
ans += getsuffsum(stateh0, stateh1);
ans += getsum(const0, const1) * mult;
ans += getprefsum(up0, up1);
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 1 0 0 1 0
1
3 7 3 5
*/
