#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
vector<long long> mosaic(vector<int> x, vector<int> y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
int n = x.size(), q = T.size();
set<int> s;
vector<vector<int>> row(3, vector<int>(n));
row[0] = x;
row[1][0] = y[1];
row[2][0] = y[2];
for (int i = 1; i < 3; i++) {
for (int j = 1; j < n; j++) {
row[i][j] = !(row[i - 1][j] | row[i][j - 1]);
if (row[i][j]) {
s.insert(i - j);
}
}
}
vector<vector<int>> col(n, vector<int>(3));
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
if (j == 0) {
col[i][j] = y[i];
continue;
}
if (i == 0) {
col[i][j] = x[j];
continue;
}
col[i][j] = !(col[i - 1][j] | col[i][j - 1]);
if (col[i][j]) {
s.insert(i - j);
}
}
}
vector<int> v;
for (auto x : s) {
v.push_back(x);
}
auto get = [&](int l, int r) {
if (l > r) swap(l, r);
auto it = ranges::upper_bound(v, r);
auto ti = ranges::lower_bound(v, l);
return it - ti;
};
vector<vector<int>> p(3, vector<int>(n + 1));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
p[i][j + 1] = p[i][j] + row[i][j];
}
}
vector<long long> ret;
for (int i = 0; i < q; i++) {
int t = T[i], b = B[i], l = L[i], r = R[i];
if (t <= 2) {
ret.push_back(p[t][r + 1] - p[t][l]);
} else {
int cur = 0;
while (l <= 2 && l <= r) {
cur += col[t][l++];
}
if (l <= r) {
int tl = t - l, tr = t - r;
cur += get(tl, tr);
}
ret.push_back(cur);
}
}
return ret;
}
