#include <bits/stdc++.h>
using namespace std;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S,
vector<int> E, vector<int> L, vector<int> R) {
vector<pair<int, int>> vpii;
for (int i = 0; i < X.size(); i++)
vpii.push_back(minmax(X[i], Y[i]));
vector<array<int, 5>> vai5;
for (int i = 0; i < S.size(); i++)
vai5.push_back({i, S[i], E[i], L[i], R[i]});
function<int(int, vector<int> &)> fvivi = [&](int cur, vector<int> &par) {
if (par[cur] == cur)
return cur;
return par[cur] = fvivi(par[cur], par);
};
int ct = -1;
function<void(int, vector<vector<int>> &, vector<int> &, vector<int> &)> dfs =
[&](int cur, vector<vector<int>> &adj, vector<int> &l, vector<int> &r) {
if (adj[cur].empty()) {
ct++;
l[cur] = r[cur] = ct;
return;
}
l[cur] = ct + 1;
for (auto a : adj[cur])
dfs(a, adj, l, r);
r[cur] = ct;
};
sort(vpii.begin(), vpii.end(),
[&](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });
vector<int> parvi1(N);
iota(parvi1.begin(), parvi1.end(), 0);
vector<vector<int>> adj1(N);
for (auto [a, b] : vpii) {
a = fvivi(a, parvi1), b = fvivi(b, parvi1);
parvi1[a] = parvi1[b] = adj1.size();
parvi1.push_back(parvi1.size());
adj1.push_back({});
adj1.back().push_back(a);
if (a != b)
adj1.back().push_back(b);
}
vector<int> l1(parvi1.size()), r1(parvi1.size());
dfs(parvi1.size() - 1, adj1, l1, r1);
parvi1 = vector<int>(N);
iota(parvi1.begin(), parvi1.end(), 0);
int in = 0;
sort(vai5.begin(), vai5.end(),
[&](array<int, 5> a, array<int, 5> b) { return a[3] > b[3]; });
vector<int> ql1(S.size()), qr1(S.size());
for (auto [a, b] : vpii) {
while (in < vai5.size() && vai5[in][3] > a) {
ql1[vai5[in][0]] = l1[fvivi(vai5[in][1], parvi1)],
qr1[vai5[in][0]] = r1[fvivi(vai5[in][1], parvi1)];
in++;
}
a = fvivi(a, parvi1), b = fvivi(b, parvi1);
parvi1[a] = parvi1[b] = parvi1.size();
parvi1.push_back(parvi1.size());
}
while (in < vai5.size()) {
ql1[vai5[in][0]] = l1[fvivi(vai5[in][1], parvi1)],
qr1[vai5[in][0]] = r1[fvivi(vai5[in][1], parvi1)];
in++;
}
vector<int> parvi2(N);
iota(parvi2.begin(), parvi2.end(), 0);
sort(vpii.begin(), vpii.end(),
[&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
vector<vector<int>> adj2(N);
for (auto [a, b] : vpii) {
a = fvivi(a, parvi2), b = fvivi(b, parvi2);
parvi2[a] = parvi2[b] = adj2.size();
parvi2.push_back(parvi2.size());
adj2.push_back({});
adj2.back().push_back(a);
if (a != b)
adj2.back().push_back(b);
}
vector<int> l2(parvi2.size()), r2(parvi2.size());
ct = -1;
dfs(parvi2.size() - 1, adj2, l2, r2);
parvi2 = vector<int>(N);
iota(parvi2.begin(), parvi2.end(), 0);
in = 0;
sort(vai5.begin(), vai5.end(),
[&](array<int, 5> a, array<int, 5> b) { return a[4] < b[4]; });
vector<int> ql2(S.size()), qr2(S.size());
for (auto [a, b] : vpii) {
while (in < vai5.size() && vai5[in][4] < b) {
ql2[vai5[in][0]] = l2[fvivi(vai5[in][2], parvi2)],
qr2[vai5[in][0]] = r2[fvivi(vai5[in][2], parvi2)];
in++;
}
a = fvivi(a, parvi2), b = fvivi(b, parvi2);
parvi2[a] = parvi2[b] = parvi2.size();
parvi2.push_back(parvi2.size());
}
while (in < vai5.size()) {
ql2[vai5[in][0]] = l2[fvivi(vai5[in][2], parvi2)],
qr2[vai5[in][0]] = r2[fvivi(vai5[in][2], parvi2)];
in++;
}
vector<array<int, 3>> order(N);
vector<pair<int, int>> points(N);
for (int i = 0; i < N; i++)
points[i] = {l1[i], l2[i]};
sort(points.begin(), points.end());
for (int i = 0; i < N; i++)
order[i] = {i, points[i].first, points[i].second};
auto ocmp = [&](array<int, 3> a, array<int, 3> b) { return a[2] < b[2]; };
sort(order.begin(), order.end(), ocmp);
vector<int> ans(L.size());
struct node {
int ct = 0;
node *l = NULL, *r = NULL;
};
vector<node *> vn;
function<node *(int, int)> build = [&](int curl, int curr) {
auto tmp = new node;
if (curl == curr) {
return tmp;
}
int mid = (curl + curr) / 2;
tmp->l = build(curl, mid), tmp->r = build(mid + 1, curr);
return tmp;
};
vn.push_back(build(0, N - 1));
function<node *(node *, int, int, int)> insert = [&](node *n, int curl,
int curr, int in) {
auto tmp = new node;
if (curl == curr) {
tmp->ct = 1;
return tmp;
}
int mid = (curl + curr) / 2;
if (in <= mid) {
tmp->r = n->r;
tmp->l = insert(n->l, curl, mid, in);
} else {
tmp->l = n->l;
tmp->r = insert(n->r, mid + 1, curr, in);
}
tmp->ct = tmp->l->ct + tmp->r->ct;
return tmp;
};
for (auto [in, x, y] : order) {
vn.push_back(insert(vn.back(), 0, N - 1, in));
}
int ql, qr;
function<int(node *, int, int)> qry = [&](node *n, int curl, int curr) {
if (curl > qr || curr < ql)
return 0;
if (ql <= curl && curr <= qr)
return n->ct;
return qry(n->l, curl, (curl + curr) / 2) +
qry(n->r, (curl + curr) / 2 + 1, curr);
};
for (int i = 0; i < S.size(); i++) {
ql = lower_bound(points.begin(), points.end(), make_pair(ql1[i], -1)) -
points.begin(),
qr = upper_bound(points.begin(), points.end(),
make_pair(qr1[i], INT_MAX)) -
points.begin() - 1;
int l = lower_bound(order.begin(), order.end(),
array<int, 3>({-1, -1, ql2[i]}), ocmp) -
order.begin(),
r = upper_bound(order.begin(), order.end(),
array<int, 3>({-1, -1, qr2[i]}), ocmp) -
order.begin();
ans[i] = min(1, qry(vn[r], 0, N - 1) - qry(vn[l], 0, N - 1));
}
return ans;
}
