#include "mosaic.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
#define pb push_back
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> lo, std::vector<int> hi) {
int n = X.size();
int q = (int)T.size();
if (n==1) return vector<ll> (q, X[0]);
assert(n==2);
vector<ll> ans(q, 0);
vector<int> all(q);
iota(all.begin(), all.end(), 0);
// sort(all.begin(), all.end(), [&](int i, int j) {
// return B[i]<B[j];
// });
// auto it = all.begin();
// while (it!=all.end() && B[*it] < 2) it++;
vector<ll> a;
for (int i=1; i<n; i++) a.pb(X[i]);
for (int i = n-2; 0<=i; i--) a[i] += a[i+1];
auto get = [&](int l, int r) {
if (r+1 == a.size()) return a[l];
return a[l] - a[r+1];
};
{
vector<ll> y;
for (int t : Y) y.pb(t);
for (int i=1; i<y.size(); i++) y[i] += y[i-1];
for (int i=0; i<q; i++) if (lo[i]==0) {
ans[i] += y[B[i]];
if (0 <= T[i]-1) ans[i] -= y[T[i]-1];
lo[i]++;
}
}
for (int r=0; r<2; r++) {
for (int i=0; i<q; i++) {
if (r==T[i] && T[i]<=B[i] && lo[i]<=hi[i]) {
T[i]++;
int L = lo[i];
int R = hi[i];
L--, R--;
ans[i] += get(L, R);
}
}
if (r+1 != n) {
vector<ll> b;
b.pb((Y[r+1]|get(0, 0))^1);
for (int i=1; i<a.size(); i++) b.pb((b.back()|get(i, i))^1);
swap(a, b);
for (int i = n-2; 0<=i; i--) a[i] += a[i+1];
}
}
return ans;
// {
// vector<ll> b = a;
// a.clear();
// for (int i=0; i<n; i++) a.pb(0);
// for (int i:b) a.pb(i);
// }
// vector<ll> b;
// {
// vector<ll> t = a;
// for (int i = n-2; 0<=i; i--) t[i] += t[i+1];
// for (int i=0; i<n; i++) b.pb(0);
// for (int i:t) b.pb(i);
// }
// int z=n;
// vector<ll> pre = {a[z]};
// auto get_one = [&](int i, int c) -> ll {
// int l = i;
// int r = i+c;
// // assert(a.size()<=r);
// if (a.size() <= r) return b[l];
// return b[l]-b[r];
// };
// auto GET = [&](int l, int r, int c) -> ll {
// if (a.size() <= r+1) return get_one(l, c);
// return get_one(l, c) - get_one(r+1, c);
// };
// for (int r=2; r<n; r++) {
// while (it!=all.end() && B[*it]==r) {
// int L = lo[*it];
// int R = hi[*it];
// int U = T[*it];
// int D = B[*it];
// if (R==0) {
// it++;
// continue;
// }
// L--; R--;
// if (L==0) {
// ans[*it] += pre.back();
// if (0 <= U-3) ans[*it] -= pre[U-3];
// L++;
// }
// if (L<=R) ans[*it] += GET(z+L, z+R, D-U+1);
// it++;
// }
// if (r+1 != n) {
// z--;
// int t = (Y[r+1]|get(z+1, z+1))^1;
// if (z+2 < a.size()) {
// a[z+1] = ((get(z+2, z+2)|t) ^ 1) + a[z+2];
// b[z+1] = b[z+2] + a[z+1];
// }
// a[z] = t + a[z+1];
// b[z] = a[z] + b[z+1];
// pre.pb(pre.back() + a[z]);
// }
// }
// return ans;
}
