#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
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){
ll n, q;
n = X.size();
q = T.size();
vll row3;
vll col3;
vl x1, y1;
for (ll i = 0; i <n; i++){
x1.push_back(X[i]);
y1.push_back(Y[i]);
}
row3.push_back(x1); col3.push_back(y1);
// Oprava: Kontrola velikosti N, aby nedošlo k přístupu mimo paměť pro N=1,2
if (n > 1) { row3.push_back({(ll)Y[1]}); }
if (n > 2) { row3.push_back({(ll)Y[2]}); }
if (n > 1) { col3.push_back({(ll)X[1]}); }
if (n > 2) { col3.push_back({(ll)X[2]}); }
for (ll i = 1; i < 3; i++){
if (i >= row3.size()) break; // Oprava: Ochrana loopu pro malé N
for (ll j = 1; j < n; j++){
ll v1 = 0; ll v2 = 0;
// Podmínka pro generování musí být bezpečná
if (row3[i][j-1] == 0 && row3[i-1][j] == 0){
v1 = 1;
}
if (col3[i][j-1] == 0 && col3[i-1][j] == 0){
v2 = 1;
}
row3[i].push_back(v1);
col3[i].push_back(v2);
}
}
vl s1, s2, s3;
// Flattening s1 (Layer 0)
for (ll i = n-1; i>=0; i--){
s1.push_back(col3[0][i]);
}
for (ll i = 1; i < n; i++){
s1.push_back(row3[0][i]);
}
// Flattening s2 (Layer 1)
if (n > 1) { // Ochrana pro malé N
for (ll i = n-1; i>=1; i--){
s2.push_back(col3[1][i]);
}
for (ll i = 2; i < n; i++){
s2.push_back(row3[1][i]);
}
}
// Flattening s3 (Layer 2+)
if (n > 2) { // Ochrana pro malé N
for (ll i = n-1; i>=2; i--){
s3.push_back(col3[2][i]);
}
for (ll i = 3; i < n; i++){
s3.push_back(row3[2][i]);
}
}
vl p1, p2, p3;
p1 = p2 = p3 = {0};
for (ll i = 0; i < s1.size(); i++){
p1.push_back(s1[i] + p1[i]);
}
for (ll i = 0; i < s2.size(); i++){
p2.push_back(s2[i] + p2[i]);
}
for (ll i = 0; i < s3.size(); i++){
p3.push_back(s3[i] + p3[i]);
}
// Oprava: Odstraněno q2. q1 nyní slouží pro vážený součet (S[i] * (i+1))
vl q1;
q1 = {0};
for (ll i = 0; i < s3.size(); i++){
q1.push_back(q1[i] + s3[i]*(i+1));
}
vl ans;
for (ll i = 0; i < q; i++){
ll l, r, u, d;
l = L[i]; r = R[i]; u = T[i]; d = B[i];
ll a, b;
ll suma = 0;
//Layer1 (Index 0)
b = 0; a = 1e9;
if (l == 0){
a = min(a, n-d-1);
b = max(b, n-u);
}
if (u == 0){
a = min(a, n + l - 1);
b = max(b, n + r);
}
if (a < b){
suma += p1[b] - p1[a];
}
//Layer2 (Index 1)
b = 0; a = 1e9;
if (l <= 1 && r >= 1){
a = min(a, n-d-1);
b = max(b, n-max(u,1ll));
}
if (u <= 1 && d >= 1){
a = min(a, n + max(l,1ll) - 3);
b = max(b, n + r - 2);
}
if (a < b && s2.size() > 0){ // check if s2 exists
// Ochrana bounds, protože s2 může být prázdné nebo kratší
a = max(0ll, a);
b = min((ll)p2.size()-1, b);
if(a < b) suma += p2[b] - p2[a];
}
// Layer3 (Recursive)
if (r >= 2 && d >= 2 && s3.size() > 0){
ll l_curr = max(2ll, l);
ll u_curr = max(2ll, u);
// Zde a, b jsou indexy do s3
ll a = l_curr - 2 + (n-1)-d;
ll b = r - 2 + n - u_curr;
// b je zde v logice kódu spíše 'poslední index', ale pro prefix sumy potřebujeme 'exclusive end'.
// V původním kódu jste používali p3[b] - p3[b-t], což naznačuje, že 'b' v array logice je exclusive bound (index + 1).
// Původní výpočet: b = r - 2 + n - u.
// Max diagonála je r - u. Index v s3 je (r-u) + n - 3.
// Vaše b = (r-u) + n - 2. To odpovídá (Index_max + 1). Takže b je správně exclusive upper bound.
ll t = min(d-u_curr, r-l_curr); // thickness (počet kroků náběhu)
// Rising slope: Sum S[i]*(dist_from_start)
// Sum_{k=0 to t-1} S[a+k]*(k+1) = (Q1[a+t] - Q1[a]) - a*(P3[a+t] - P3[a])
suma += q1[a+t] - q1[a];
suma -= (p3[a+t] - p3[a])*a;
// Constant plateau: Sum S[i]*(t+1)
// Range [a+t, b-t) (exclusive end)
if (a+t < b-t) {
suma += (p3[b-t] - p3[a+t])*(t+1);
}
// Falling slope: Sum S[i]*(dist_from_end)
// Range [b-t, b). Váhy t, t-1, ..., 1.
// Vzorec: (b+1)*Sum(S) - Sum(S*i)
// = (b+1)*(P3[b] - P3[b-t]) - (Q1[b] - Q1[b-t])
// Oprava: Nahrazení chybné q2 logiky tímto vzorcem
suma += (b+1)*(p3[b] - p3[b-t]);
suma -= (q1[b] - q1[b-t]);
}
ans.push_back(suma);
}
return ans;
}
/*/int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Test case
vector<int> X {1, 0, 1, 0, 1};
vector<int> Y {1, 1, 0, 1, 0};
vector<int> T {1};
vector<int> B {3};
vector<int> L {1};
vector<int> R {3};
// Expected based on manual trace or constraints
vl ans = mosaic(X, Y, T, B, L, R);
for (auto x : ans){
cout << x << "\n";
}
return 0;
}
/*/
