#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
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) {
int n = X.size();
int q = T.size();
bool x[4][n];
bool y[n][4];
for (int i = 0; i < n; ++i)
{
x[0][i]=X[i];
y[i][0]=Y[i];
}
for (int i = 0; i < 4; ++i)
{
x[i][0]=Y[i];
y[0][i]=X[i];
}
for (int i = 1; i < 4; ++i)
{
for (int j = 1; j < n; ++j)
{
if(x[i-1][j]+x[i][j-1]==0) x[i][j]=1;
else x[i][j]=0;
}
}
for (int i = 1; i < n; ++i)
{
for (int j = 1; j < 4; ++j)
{
if(y[i-1][j]+y[i][j-1]==0) y[i][j]=1;
else y[i][j]=0;
}
}
int prefx[4][n];
int prefy[n][4];
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < n; ++j)
{
prefx[i][j]=x[i][j];
if(j) prefx[i][j]+=prefx[i][j-1];
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 4; ++j)
{
prefy[i][j]=y[i][j];
if(j) prefy[i][j]+=prefy[i][j-1];
}
}
vector<long long> ans;
int pre[n];
for (int i = 0; i < n; ++i)
{
pre[i]=y[i][3];
if(i) pre[i]+=pre[i-1];
}
for (int k = 0; k < q; ++k)
{
int t=T[k];
int i=L[k];
int j=R[k];
if(t<=3) ans.push_back(prefx[t][j]-(i ? prefx[t][i-1] : 0));
else if (j<=3) ans.push_back(prefy[t][j]-(i ? prefy[t][i-1] : 0));
else{
int cur = 0;
int up = t - 3;
if(i<=3){
cur+=prefy[t][3]-(i ? prefy[t][i-1] : 0);
i=4;
}
if(j-up>=3&&i-up>=3) cur+=prefx[3][j-up]-prefx[3][i-up-1];
else if(j-up>=3){
cur+=prefx[3][j-up]-prefx[3][3];
cur+=pre[t-(i-3)]-pre[2];
}
else{
cur-=pre[t-(j-3)];
cur+=pre[t-(i-3)];
}
ans.push_back(cur);
}
}
return ans;
}
