#include "mosaic.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
struct BIT
{
    ll tree[N];
    int n;
    void init(int m)
    {
        n = m;
        int i;
        for(i = 1; i <= n; i++)
            tree[i] = 0;
    }
    void add(int x, ll y)
    {
        while(x <= n)
        {
            tree[x] += y;
            x += (x & -x);
        }
    }
    ll qry(int x)
    {
        ll ans = 0;
        while(x)
        {
            ans += tree[x];
            x -= (x & -x);
        }
        return ans;
    }
    ll qlr(int l, int r)
    {
        l = max(l, 1);
        r = min(r, n);
        if(l > r)
            return 0;
        return qry(r) - qry(l - 1);
    }
};
BIT qwq[4];
int row[4][N], col[N][4], sr[4][N], sc[N][4], n;
ll sum(int x, int y)
{
    if(x < 0 || y < 0)
        return 0;
    if(x < 3)
        return sr[x][y];
    if(y < 3)
        return sc[x][y];
    ll res = sr[2][y] + sc[x][2] - sr[2][2], a;
    if(row[2][2])
        res += min(x - 2, y - 2);
    a = y - x + 2;
    res += qwq[0].qlr(1, a) * (x - 2) + qwq[0].qlr(a + 1, n) * y - qwq[1].qlr(a + 1, n);
    a = x - y + 2;
    res += qwq[2].qlr(1, a) * (y - 2) + qwq[2].qlr(a + 1, n) * x - qwq[3].qlr(a + 1, n);
    return res;
}
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R)
{
    n = X.size();
    int q = T.size(), i, j;
    vector<ll> C(q, 0);
    for(i = 0; i < n; i++)
        row[0][i] = X[i];
    for(i = 0; i < n; i++)
        col[i][0] = Y[i];
    for(i = 0; i < 3; i++)
    {
        row[i][0] = col[i][0];
        col[0][i] = row[0][i];
    }
    for(i = 1; i < 3; i++)
        for(j = 1; j < n; j++)
            row[i][j] = (!row[i - 1][j] && !row[i][j - 1]);
    for(i = 1; i < n; i++)
        for(j = 1; j < 3; j++)
            col[i][j] = (!col[i - 1][j] && !col[i][j - 1]);
    for(i = 0; i < 3; i++)
        for(j = 0; j < n; j++)
            sr[i][j] = row[i][j];
    for(i = 0; i < 3; i++)
        for(j = 1; j < n; j++)
            sr[i][j] += sr[i][j - 1];
    for(i = 1; i < 3; i++)
        for(j = 0; j < n; j++)
            sr[i][j] += sr[i - 1][j];
    for(i = 0; i < n; i++)
        for(j = 0; j < 3; j++)
            sc[i][j] = col[i][j];
    for(i = 0; i < n; i++)
        for(j = 1; j < 3; j++)
            sc[i][j] += sc[i][j - 1];
    for(i = 1; i < n; i++)
        for(j = 0; j < 3; j++)
            sc[i][j] += sc[i - 1][j];
    for(i = 0; i < 4; i++)
        qwq[i].init(n);
    for(i = 3; i < n; i++)
        if(row[2][i])
        {
            qwq[0].add(i, 1);
            qwq[1].add(i, i);
        }
    for(i = 3; i < n; i++)
        if(col[i][2])
        {
            qwq[2].add(i, 1);
            qwq[3].add(i, i);
        }
    for(i = 0; i < q; i++)
        C[i] = sum(B[i], R[i]) - sum(T[i] - 1, R[i]) - sum(B[i], L[i] - 1) + sum(T[i] - 1, L[i] - 1);
    return C;
}