#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
const int maxn = 2e5 + 5;
const int N = 4e5 + 5;

int n, q, len;
bool rw[maxn][4], cl[maxn][4], arr[N];
int pr[maxn][4], pc[maxn][4], sum[N];
ll sum2[N];

ll calc(int l, int r) { return sum2[r] - sum2[l - 1] - 1ll * (l - 1) * (sum[r] - sum[l - 1]); }
vector<ll> mosaic(vi X, vi Y, vi T, vi B, vi L, vi R)
{
	n = X.size(), q = T.size();
	X.resize(n + 1), Y.resize(n + 1);
	for (int i = n; i; i--) X[i] = X[i - 1]; X[0] = 0;
	for (int i = n; i; i--) Y[i] = Y[i - 1]; Y[0] = 0;
	if (n <= 2)
	{
		vector<ll> res; res.resize(q);
		for (int Q = 0; Q < q; Q++)
		{
			int l = L[Q] + 1, r = R[Q] + 1, x = T[Q] + 1, y = B[Q] + 1; ll ans = 0;
			for (int i = x; i <= y; i++)
				for (int j = l; j <= r; j++)
					if (i == 1 && j == 1) ans += X[1];
					else if (i == 2 && j == 2) ans += (!X[2] && !Y[2]);
					else ans += (i == 2 ? Y[2] : X[2]);
			res[Q] = ans;
		}
		return res;
	}
	
	for (int i = 1; i <= n; i++) rw[i][1] = Y[i], cl[i][1] = X[i];
	rw[1][2] = X[2], cl[1][2] = Y[2]; rw[1][3] = X[3], cl[1][3] = Y[3];
	for (int j = 2; j <= 3; j++)
		for (int i = 2; i <= n; i++) rw[i][j] = !rw[i - 1][j] && !rw[i][j - 1], cl[i][j] = !cl[i - 1][j] && !cl[i][j - 1];
	for (int j = 1; j <= 3; j++)
		for (int i = 1; i <= n; i++) pr[i][j] = pr[i - 1][j] + rw[i][j], pc[i][j] = pc[i - 1][j] + cl[i][j];
	int len = 2 * n - 5;
	for (int i = 1; i <= n - 2; i++) arr[i] = rw[n - i + 1][3];
	for (int i = n - 1; i <= len; i++) arr[i] = cl[i - (n - 5)][3];
	for (int i = 1; i <= len; i++) sum[i] = sum[i - 1] + arr[i], sum2[i] = sum2[i - 1] + (arr[i] ? i : 0);

	vector<ll> res; res.resize(q);
	for (int Q = 0; Q < q; Q++)
	{
		int l = L[Q] + 1, r = R[Q] + 1, x = T[Q] + 1, y = B[Q] + 1; ll ans = 0;
		for (int i = x; i <= 2; i++) ans += pc[r][i] - pc[l - 1][i];
		if (y <= 2) { res[Q] = ans; continue; }
		for (int i = l; i <= 2; i++) ans += pr[y][i] - pr[2][i];
		if (r <= 2) { res[Q] = ans; continue; }

		l = max(l, 3), x = max(x, 3);
		int p1 = l - y + n - 2, p2 = l - x + n - 2, p3 = r - y + n - 2, p4 = r - x + n - 2, dis = min(r - l, y - x);
		if (p2 > p3) swap(p2, p3);
		ans += 1ll * (sum[p3 - 1] - sum[p2]) * dis;
		ans += calc(p1, p2) + 1ll * (dis + 1) * (sum[p4] - sum[p3 - 1]) - calc(p3, p4);
		res[Q] = ans;
	}
	return res;
}