#include "mosaic.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int s = 3;
const bool stres = 0;
int n , q;
vector<ll> suf , sufi , prei , vec;
int get(int x , int y , int n){
return 0;
}
int f(int x , int y) { return ((x == 0) and (y == 0)); }
vector<long long> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r) {
n = x.size();
if(n < s){
for(int i = n;i < s; ++ i) x.push_back(0) , y.push_back(0);
n = s;
}
q = t.size();
//cout << q << ' ';
vector<ll> ans(q , 0);
for(int c = 0;c < s; ++ c){
vec = {} , suf = vector<ll> (2 * n , 0);
//for(auto to : x) cout << to << ' ';
//cout << '\n';
//for(auto to : y) cout << to << ' ';
//cout << '\n';
for(int i = y.size() - 1; i >= 0; -- i) vec.push_back(y[i]);
for(int i = 1;i < x.size(); ++ i) vec.push_back(x[i]);
for(int i = 0;i < vec.size(); ++ i) suf[i + 1] = suf[i] + vec[i];
for(int i = 0;i < q; ++ i){
if(t[i] <= b[i] and l[i] <= r[i]){
if(t[i] == 0){
ans[i] += suf[r[i] + n] - suf[l[i] + n - 1];
}
if(l[i] == 0){
ans[i] += suf[n - t[i]] - suf[n - b[i] - 1];
}
if(l[i] == 0 and t[i] == 0) ans[i] -= vec[n - 1];
t[i] = max(0 , t[i] - 1);
b[i] --;
l[i] = max(0 , l[i] - 1);
r[i] --;
}
}
vector<int> nx , ny;
nx.push_back(f(x[1] , y[1]));
ny.push_back(f(x[1] , y[1]));
for(int i = 2;i < x.size(); ++ i) nx.push_back(f(nx.back() , x[i]));
for(int i = 2;i < y.size(); ++ i) ny.push_back(f(ny.back() , y[i]));
x = nx;
y = ny;
n --;
}
sufi = prei = vector<ll> (2 * n + 1 , 0);
sufi[0] = 0;
for(int i = 1;i < 2 * n; ++ i){
suf[i] = suf[i - 1] + vec[i - 1] * i;
}
prei[2 * n - 1] = 0;
for(int i = 2 * n - 2; i >= 0; -- i){
prei[i] = prei[i + 1] + vec[i] * (2 * n - 1 - i);
}
for(int i = 0;i < q; ++ i){
if(t[i] <= b[i] and l[i] <= r[i]){
int l1 = n - 1 - b[i] + l[i] , r1 = n - 1 - t[i] + r[i];
l1 ++ , r1 ++;
int x = min(b[i] - t[i] + 1 , r[i] - l[i] + 1);
int r2 = l1 + x - 1;
int l2 = r1 - x + 2;
//cout << l1 << ' ' << r2 << ' ' << l2 << ' ' << r2 << '\n';
if(l1 <= r2){
ans[i] += (sufi[r2] - sufi[l1 - 1]) - (l1 - 1) * (suf[r2] - suf[l1 - 1]);
ans[i] += (prei[l2 - 1] - prei[r1]) - (r1 - 2 * n - 2) * (suf[r1] - suf[l2 - 1]);
}
ans[i] += ((b[i] - t[i] + 1) + (r[i] - l[i] + 1) - 1) * (suf[l2 - 1] - suf[r2]);
}
}
return ans;
}
