#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R) {
int n = sz(X);
if(n == 1){
int k = sz(T);
vector<long long>cevap(k);
for(int i = 0;i<k;i++){
cevap[i] = X[0];
}
return cevap;
}
else if(n == 2){
int k = sz(T);
vector<long long>cevap(k);
int grid[2][2];
grid[0][0] = X[0];
grid[0][1] = X[1];
grid[1][0] = Y[1];
grid[1][1] = !grid[0][1] and !grid[1][0];
// cout << grid[0][0] << " " << grid[0][1] << endl;
// cout << grid[1][0] << " " << grid[1][1] << endl;
for(int i = 0;i<k;i++){
for(int j = T[i];j<=B[i];j++){
for(int j2 = L[i];j2<=R[i];j2++){
cevap[i] += grid[j][j2];
}
}
}
return cevap;
}
vector<vector<int>>grid(n);
grid[0] = vector<int>(n);
grid[1] = vector<int>(n);
grid[2] = vector<int>(n);
for(int i = 3;i<n;i++){
grid[i] = vector<int>(3);
}
for(int i = 0;i<n;i++){
grid[0][i] = X[i];
grid[i][0] = Y[i];
}
// cout << "flag0" << endl;
// ilk iki satiri simule et ve prefix sum yap
vector<int> presat(n);
presat[0] = Y[2];
for(int i = 1;i<n;i++){
grid[1][i] = !grid[1][i-1] and !grid[0][i];
grid[2][i] = !grid[2][i-1] and !grid[1][i];
presat[i] = grid[2][i] + presat[i-1];
}
vector<long long>presat2(n);// n n-1 n-2 ile carpilmis presum
presat2[0] = grid[2][0] * n;
for(int i = 1;i<n;i++){
presat2[i] = presat2[i-1] + grid[2][i] * (n - i);
}
// cout << "flag1" << endl;
// ilk iki sutunu simule et ve prefix sum yap
vector<int> presut(n);
presut[0] = X[2];
for(int i = 1;i<n;i++){
grid[i][1] = !grid[i-1][1] and !grid[i][0];
grid[i][2] = !grid[i-1][2] and !grid[i][1];
presut[i] = grid[i][2] + presut[i-1];
}
vector<long long>presut2(n);// n n-1 n-2 ile carpilmis presum
presut2[0] = grid[0][2] * n;
for(int i = 1;i<n;i++){
presut2[i] = presut2[i-1] + grid[i][2] * (n - i);
}
// gridi pref sumla
vector<vector<int>>gridsum = grid;
for(int i = 0;i<n;i++){
for(int j = 0;j<sz(grid[i]);j++){
if(i)gridsum[i][j] += gridsum[i-1][j];
if(j)gridsum[i][j] += gridsum[i][j-1];
if(i and j)gridsum[i][j] -= gridsum[i-1][j-1];
}
}
auto getsum = [&](int x , int y){
if(x < 0 or y < 0)return 0ll;
// cout << "getsum : " << x << " " << y << endl;
long long ret = 0;
// ilk sutun ve satir
ret += gridsum[min(x,1)][y];
ret += gridsum[x][min(y,1)];
ret -= gridsum[min(x,1)][min(y,1)];
// cout << "ret1 : " << ret << endl;
if(x > 1 and y > 1){
// satir
{
int diff = max(0 , y - x);
long long term1 = presat2[y] - presat2[diff+1];
long long term2 = (long long)(presat[y] - presat[diff+1]) * (long long)(n - y - 1);
ret += term1 - term2;
// cout << "term1 - term2 : " << term1 - term2 << endl;
long long term3 = (long long)(presat[diff+1] - presat[1]) * (long long)(min(x,y) - 1);
ret += term3;
// cout << "term3 : " << term3 << endl;
// cout << "ret2 : " << ret << endl;
}
// sutun
{
int diff = max(0 , x - y);
long long term1 = presut2[x] - presut2[diff+1];
long long term2 = (long long)(presut[x] - presut[diff+1]) * (long long)(n - x - 1);
ret += term1 - term2;
long long term3 = (long long)(presut[diff+1] - presut[1]) * (long long)(min(x,y) - 1);
ret += term3;
// cout << "ret3 : " << ret << endl;
}
ret -= (long long)grid[2][2] * (long long)(min(x,y) - 1);
}
// cout << "ret : " << ret << endl;
return ret;
};
auto getrect = [&](int lx , int rx , int ly , int ry){
return getsum(rx,ry) - getsum(lx-1,ry) - getsum(rx,ly-1) + getsum(lx-1,ly-1);
};
int k = sz(T);
vector<long long>cevap(k);
for(int i = 0;i<k;i++){
cevap[i] = getrect(T[i] , B[i] , L[i] , R[i]);
}
return cevap;
}
