#include "mosaic.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 1e6 + 100 , sq = 20 , inf = 1e9 , mod = 998244353;
vector <ll> a[maxn] , s[maxn] ;
ll fen[maxn] ,n ,b[maxn];
int ch(int x, int y){
if(x+y==0)return 1;
return 0 ;
}
void upd(int x, int w){
x++;
while(x <= 2*n+3){
fen[x] += w;
x += x&-x ;
}
}
ll que(int x){
ll ans = 0;
x++;
while(x){
ans += fen[x] ;
x -= x&-x ;
}
return ans;
}
vector <int> vec[maxn] ;
ll sm[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) {
n = sz(X) ;
rep(i , 0 ,n-1){
if(i <= sq+2){
rep(j , 0, n-1){a[i].pb(0);s[i].pb(0);}
}else{
rep(j , 0 ,sq+50){a[i].pb(0);s[i].pb(0);}
}
}
rep(i , 0 , n-1){
a[0][i] = X[i] ;
a[i][0] = Y[i] ;
}
rep(i , 1, n-1){
rep(j ,1, n-1){
if(i > sq && j > sq)break ;
if(a[i-1][j]==0 && a[i][j-1]==0){
a[i][j] = 1;
}else{
a[i][j] = 0 ;
}
}
}
rep(i , 0, n-1){
rep(j , 0 ,n-1){
if(i > sq&& j > sq)break ;
s[i][j] = a[i][j] ;
if(i)s[i][j] += s[i-1][j] ;
if(j)s[i][j] += s[i][j-1];
if(i&&j)s[i][j] -= s[i-1][j-1] ;
}
}
vector <ll> C ;
rep(i , 0 , sz(T)-1){
if(T[i] <= sq){
ll ans = s[B[i]][R[i]] ;
if(L[i])ans -= s[B[i]][L[i]-1] ;
if(T[i])ans -= s[T[i]-1][R[i]] ;
if(L[i] && T[i])ans += s[T[i]-1][L[i]-1] ;
sm[i] = ans;
}else{
sm[i] =0 ;
while(L[i] <= sq && L[i] <= R[i]){
sm[i] += a[T[i]][L[i]] ;
L[i]++ ;
}
if(L[i] > R[i])continue ;
vec[T[i]].pb(i) ;
}
}
rep(i ,sq , n-1){
b[i+n] = a[sq][i] ;
upd(i+n , b[i+n]) ;
}
int l = sq+n , r= n+n-1 ;
// cout << 20 << " : " ;
// rep(i , l, r)cout <<b[i] ;
// cout << "\n";
rep(i , sq+1 ,n-1){
b[l-1] = ch(a[i][sq-1] , b[l]) ;
l--;
r-- ;
//cout << i << " : " ;
// rep(i , l, r)cout <<b[i] ;
// cout << "\n";
upd(l , b[l]) ;
for(int x : vec[i]){
// cout << que(l+R[x]-sq) << " " << que(l+L[x]-sq - 1) << "<--\n";
sm[x] += que(l+R[x]-sq) -que(l+L[x]-sq - 1); ;
}
}
rep(i , 0 ,sz(T)-1){
C.pb(sm[i]) ;
}
return C;
}
