#include <bits/stdc++.h>

using LL = long long;

constexpr int N = 200005, W = 10;

int n, q, h0[W][N], h1[N][W];
LL a[2 * N], b[2 * N];

std::vector<LL> 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
) {
    n = X.size();
    q = T.size();
    std::vector<LL> ans(q);
    if (n < W) {
        std::vector<std::vector<int>> h(n, std::vector<int>(n));
        for (int i = 0; i < n; i++) {
            h[0][i] = X[i];
            h[i][0] = Y[i];
        }
        for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) h[i][j] = !(h[i - 1][j] | h[i][j - 1]);
        for (int i = 0; i < q; i++) {
            for (int x = T[i]; x <= B[i]; x++) for (int y = L[i]; y <= R[i]; y++)
                ans[i] += h[x][y];
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            h0[0][i] = X[i];
            h1[i][0] = Y[i];
        }
        for (int i = 1; i < W; i++) {
            h0[i][0] = Y[i];
            h1[0][i] = X[i];
            for (int j = 1; j < n; j++) {
                h0[i][j] = !(h0[i - 1][j] | h0[i][j - 1]);
                h1[j][i] = !(h1[j - 1][i] | h1[j][i - 1]);
            }
        }
        for (int i = W - 1, j = W - 1; j < n; j++) a[j - i + N] += h0[i][j];
        for (int j = W - 1, i = W; i < n; i++) a[j - i + N] += h1[i][j];
        for (int i = 1; i < 2 * N; i++) {
            a[i] += a[i - 1];
            b[i] = b[i - 1] + a[i];
        }
        const auto calc = [&](int x, int y, int len) { return (b[y + len - 1] - b[y - 1]) - (b[x + len - 1] - b[x - 1]); };
        for (int i = 0; i < q; i++) {
            int x = T[i] - B[i] + 1, y = R[i] - L[i] + 1;
            if (x <= y) {
                ans[i] += calc(L[i] - B[i] + N, L[i] - T[i] + N, x - 1);
                ans[i] += calc((R[i] - (x - 1)) - B[i] + N, R[i] - B[i] + N, x - 1);
                ans[i] += calc(L[i] - B[i] + N - 1, (R[i] - (x - 1)) - B[i] + N, y);
            }
            else {
                ans[i] += calc(L[i] - (B[i] + (y - 1)) + N, L[i] - T[i] + N, y - 1);
                ans[i] += calc(L[i] - B[i] + N, R[i] - B[i] + N, y - 1);
                ans[i] += calc(L[i] - B[i] + N - 1, R[i] - (B[i] - (y - 1)) + N, x);
            }
        }
    }
    return ans;
}
/*
1010
1001
0100
1010
*/