#include <bits/stdc++.h>
using namespace std;
vector<long long>
mosaic(vector<int> X, std::vector<int> Y, vector<int> T, std::vector<int> B, vector<int> L, std::vector<int> R) {
vector<long long> ans;
int n = (int) X.size(), q = (int) T.size();
unordered_map<int, unordered_map<int, long long>> a, b;
unordered_map<int, long long> s;
for (int i = 0; i < n; ++i) a[0][i] = X[i];
for (int i = 0; i < n; ++i) a[i][0] = Y[i];
for (int i = 1; i < 3; ++i) for (int j = 1; j < n; ++j) a[i][j] = !a[i - 1][j] && !a[i][j - 1];
for (int j = 1; j < 3; ++j) for (int i = 1; i < n; ++i) a[i][j] = !a[i - 1][j] && !a[i][j - 1];
b = a;
for (int i = n - 1; i > 1; --i) s[i] = a[2][i];
for (int i = 3; i < n; ++i) s[4 - i] = a[i][2];
for (int i = n - 2; i > 4 - n; --i) s[i] += s[i + 1];
for (int i = n - 2; i > 4 - n; --i) s[i] += s[i + 1];
for (int j = 0; j < 3; ++j) for (int i = 1; i < n; ++i) b[i][j] += b[i - 1][j];
for (int j = 0; j < 3; ++j) for (int i = 1; i < n; ++i) a[j][i] += a[j][i - 1];
for (int i = 0; i < q; ++i) {
long long c = 0;
while (T[i] <= B[i] && T[i] < 3) c += a[T[i]][R[i]] - a[T[i]++][L[i] - 1];
while (L[i] <= R[i] && L[i] < 3) c += b[B[i]][L[i]] - b[T[i] - 1][L[i]++];
if (T[i] <= B[i] && L[i] <= R[i]) {
L[i] -= B[i] - 2;
R[i] -= B[i] - 2;
c += s[L[i]] - s[R[i] + 1] - s[L[i] + B[i] - T[i] + 1] + s[R[i] + B[i] - T[i] + 2];
}
ans.emplace_back(c);
}
return ans;
}
//int main() {
//// for (long long i: mosaic({1, 0, 1, 1, 0}, {1, 1, 0, 1, 1},
//// {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4},
//// {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4},
//// {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4},
//// {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4}))
//// cout << i;
//// for (long long i: mosaic({1, 0, 1, 1, 0}, {1, 1, 0, 1, 1},
//// {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4}, {0, 0, 0, 0, 0}, {4, 4, 4, 4, 4}))
//// cout << i;
// cout << mosaic({0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {8}, {9}, {9}, {9})[0];
// return 0;
//}
/*
10110
10001
01010
10101
10010
*/
/*
0000000000
0101010101
0010101010
0101010101
0010101010
0101010101
0010101010
0101010101
0010101010
0101010101
*/
