#include <bits/stdc++.h>

using LL = long long;

constexpr int N = 200005, W = 5;

int n, q, h0[W][N], h1[N][W];
LL a[2 * N], b[2][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 = 0; i < W; i++) for (int j = 1; j < N; j++) {
            h0[i][j] += h0[i][j - 1];
            h1[j][i] += h1[j - 1][i];
        }
        for (int i = 1; i < 2 * N; i++) {
            b[0][i] = b[0][i - 1] + a[i - 2];
            a[i] += a[i - 2];
            b[1][i] = b[1][i - 1] + a[i];
        }
        const auto calc = [&](int x, int y, int len) { return (b[1][y + len - 1] - b[1][y - 1]) - (b[0][x + len - 1] - b[0][x - 1]); };
        for (int i = 0; i < q; i++) {
            while (T[i] <= B[i] && T[i] < W) {
                ans[i] += h0[T[i]][R[i]] - (L[i] ? h0[T[i]][L[i] - 1] : 0);
                T[i]++;
            }
            while (L[i] <= R[i] && L[i] < W) {
                ans[i] += h1[B[i]][L[i]] - (T[i] ? h1[T[i] - 1][L[i]] : 0);
                L[i]++;
            }
            if (T[i] <= B[i] && L[i] <= R[i]) {
                int x = B[i] - T[i] + 1, y = R[i] - L[i] + 1;
                if (x <= y) {
                    ans[i] += calc(L[i] - (T[i] + (x - 1) - 1) + N, L[i] - T[i] + N, x - 1);
                    ans[i] += calc((R[i] - (x - 1) + 1) - B[i] + N, R[i] - B[i] + N, x - 1);
                    ans[i] += calc(L[i] - B[i] + N, (L[i] + (x - 1)) - T[i] + N, y - (x - 1));
                }
                else {
                    ans[i] += calc(L[i] - (T[i] + (y - 1) - 1) + N, L[i] - T[i] + N, y - 1);
                    ans[i] += calc((R[i] - (y - 1) + 1) - B[i] + N, R[i] - B[i] + N, y - 1);
                    ans[i] += calc(L[i] - B[i] + N, R[i] - (B[i] - (y - 1)) + N, x - (y - 1));
                }
            }
        }
    }
    return ans;
}