#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];
long long pref[6][maxn];
long long prefy[maxn];
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 <= 4; ++ 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 (long long i = 1; i <= 4; ++ i)
{
for (long long j = 1; j <= n; ++ j)
pref[i][j] = pref[i][j-1] + a[i][j];
}
vector < long long > res;
// return res;
prefy[1] = a[4][4];
for (long long i = 2; i <= n-3; ++ i)
prefy[i] = prefy[i-1] + a[i+3][4];
q = (long long)T.size();
//std::vector<long long> C(q, 0);
for (long long i = 0; i < q; ++ i)
{
long long row = T[i] + 1;
long long l = L[i] + 1;
long long r = R[i] + 1;
long long col = l;
long long ans = 0;
if(row <= 4)
{
res.pb(pref[row][r] - pref[row][l-1]);
continue;
}
if(col < 4)
{
for (long long j = l; j < min(1LL * 4, r+1); ++ j)
ans += a[row][j];
col = 4;
}
if(col > r)
{
res.pb(ans);
continue;
}
l = col;
long long pl = max(l, row);
long long pr = r;
long long start_point = (pl - row) + 1;
long long sz = pr - pl + 1;
long long end_point = start_point + sz - 1;
if(start_point <= end_point)
ans += pref[4][end_point] - pref[4][start_point-1];
r = min(r, row - 1);
/// l to r v prefy
if(l <= r)
{
long long st = (row - l) + 1;
long long ed = 2;
ans += prefy[st] - prefy[ed-1];
}
res.pb(ans);
}
return res;
}
/**
4
1 0 1 0
1 1 0 1
2
0 3 0 3
2 3 0 2
*/
