#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
typedef pair <int, int> pii;
int n, q;
int a[N], b[N], col[N];
struct Node {
	int l, r, id, w;
} ;
vector <Node> t[N];
vector <pii> S;
struct Mat {
	int n, m;
	LL a[3][3];
	Mat operator + (const Mat &B) {
		Mat res; res.n = n; res.m = m;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				res.a[i][j] = a[i][j] + B.a[i][j];
		return res;
	}
	Mat operator * (const Mat &B) {
		Mat res; res.n = n; res.m = B.m;
		memset(res.a, 0, sizeof(res.a));
		for (int i = 0; i < n; i++)
			for (int k = 0; k < m; k++)
				for (int j = 0; j < B.m; j++)
					res.a[i][j] += a[i][k] * B.a[k][j];
		return res;
	}
} clr, rev, upd;
struct Seg {
	#define lx x << 1
	#define rx x << 1 | 1
	Mat t[N << 2], tag[N << 2];
	void upd(int x, const Mat &w) {
		t[x] = t[x] * w;
		tag[x] = tag[x] * w;
	}
	void pushup(int x) {
		t[x] = t[lx] + t[rx];
	}
	void pushdown(int x) {
		upd(lx, tag[x]);
		upd(rx, tag[x]);
		tag[x] = clr;
	}
	void build(int x, int L, int R) {
		tag[x] = clr;
		if (L == R) {
			t[x].a[0][0] = t[x].a[0][1] = a[L]; t[x].a[0][2] = 1;
			t[x].n = 1; t[x].m = 3; return;
		}
		int mid = L + R >> 1;
		build(lx, L, mid);
		build(rx, mid + 1, R);
		pushup(x);
	}
	void modify(int x, int pos, int w, int L, int R) {
		if (L == R) return void(t[x].a[0][1] = w);
		pushdown(x);
		int mid = L + R >> 1;
		if (pos <= mid) modify(lx, pos, w, L, mid);
		else modify(rx, pos, w, mid + 1, R);
		pushup(x);
	}
	void change(int x, int l, int r, const Mat &w, int L, int R) {
		if (l <= L && R <= r) return upd(x, w);
		pushdown(x);
		int mid = L + R >> 1;
		if (l <= mid) change(lx, l, r, w, L, mid);
		if (r > mid) change(rx, l, r, w, mid + 1, R);
		pushup(x);
	}
	LL query(int x, int l, int r, int L, int R) {
		if (l <= L && R <= r) return t[x].a[0][0];
		pushdown(x);
		int mid = L + R >> 1; LL res = 0;
		if (l <= mid) res += query(lx, l, r, L, mid);
		if (r > mid) res += query(rx, l, r, mid + 1, R);
		return res;
	}
} seg;
vector <LL> mosaic(vector <int> X, vector <int> Y, vector <int> T, vector <int> B, vector <int> L, vector <int> R) {
	n = X.size(); q = T.size(); vector <LL> Ans(q);
	for (int i = 0; i < n; i++) a[i + 1] = X[i], b[i + 1] = Y[i];
	for (int i = 0; i < q; i++) {
		Node w; w.l = L[i] + 1; w.r = R[i] + 1; w.id = i;
		if (T[i]) {
			w.w = -1;
			t[T[i]].push_back(w);
		}
		w.w = 1; t[B[i] + 1].push_back(w);
	}
	for (int i = 2; i <= n; i++) S.push_back(make_pair(i, i)), col[i] = a[i];
	memset(clr.a, 0, sizeof(clr.a));
	clr.n = clr.m = 3; clr.a[0][0] = clr.a[1][1] = clr.a[2][2] = 1;
	rev = clr; rev.a[1][1] = -1; rev.a[2][1] = 1; upd = clr; upd.a[1][0] = 1;
	seg.build(1, 1, n);
	for (auto p : t[1]) Ans[p.id] += p.w * seg.query(1, p.l, p.r, 1, n);
	for (int i = 2; i <= n; i++) {
		int c = b[i], lst = 0; seg.modify(1, 1, c, 1, n);
		vector <pii> tmp;
		for (auto p : S) {
			if (col[p.first]) {
				seg.change(1, p.first, p.second, rev, 1, n);
				col[p.first] = 0;
				if (c == col[p.first] && lst) {
					tmp.push_back(make_pair(lst, p.first - 1));
					lst = p.first;
				}
				if (!lst) lst = p.first;
				c = col[p.first] ^ ((p.second - p.first) & 1);
			}
			else {
				if (!c) {
					seg.change(1, p.first, p.second, rev, 1, n);
					col[p.first] = 1;
					if (c == col[p.first] && lst) {
						tmp.push_back(make_pair(lst, p.first - 1));
						lst = p.first;
					}
					if (!lst) lst = p.first;
					c = col[p.first] ^ ((p.second - p.first) & 1);
				}
				else {
					if (p.first < p.second) seg.change(1, p.first + 1, p.second, rev, 1, n), col[p.first + 1] = 0;
					if (p.first < p.second) {
						if (!lst) tmp.push_back(make_pair(p.first, p.first));
						else tmp.push_back(make_pair(lst, p.first));
					}
					if (p.first == p.second) c = 0, lst = p.first;
					else c = (p.second - p.first + 1) & 1, lst = p.first + 1;
				}
			}
		}
		if (lst) tmp.push_back(make_pair(lst, n)); swap(S, tmp);
		seg.change(1, 1, n, upd, 1, n);
		for (auto p : t[i]) Ans[p.id] += p.w * seg.query(1, p.l, p.r, 1, n);
	}
	return Ans;
}