#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
int n;
struct Tree {
int root[N];
int par[18][N];
vector<int> g[N];
vector<pair<int, int>> edge;
int tin[N], tout[N], tt;
void add(int u,int v) {
edge.emplace_back(u, v);
}
void dfs(int u, int p) {
par[0][u] = p;
tin[u] = ++tt;
for (int i = 1; i < 18; ++i) par[i][u] = par[i - 1][par[i - 1][u]];
for (int v : g[u]) {
dfs(v, u);
}
tout[u] = tt;
}
int anc(int u) {
return root[u] == u ? u : root[u] = anc(root[u]);
}
void build() {
for (int i = 0; i < n; ++i) root[i] = i;
sort(edge.begin(), edge.end());
for (auto e : edge) {
int u = abs(e.first), v = abs(e.second);
u = anc(u), v = anc(v);
if (u ^ v) {
g[u].push_back(v);
root[v] = u;
}
}
}
int getL(int u,int l) {
for (int i = 17; i >= 0; --i) {
if (par[i][u] >= l) u = par[i][u];
}
return u;
}
int getR(int u,int r) {
for (int i = 17; i >= 0; --i) {
if (par[i][u] <= r) u = par[i][u];
}
return u;
}
} pre, suf;
int ft[N];
void add(int p) {
for (; p <= n; p += p & -p) ft[p]++;
}
int get(int p) {
int ans = 0;
for (; p > 0; p -= p & -p) ans += ft[p];
return ans;
}
int get(int l,int r) {
return get(r) - get(l - 1);
}
struct Query {
int l, r, id, sgn;
Query(int l = 0,int r = 0,int id = 0,int sgn = 0) : l(l), r(r), id(id), sgn(sgn) {}
bool operator < (const Query &q) const {
return r < q.r;
}
};
int ans[N];
vector<int> check_validity(int n,vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l,vector<int> r) {
::n = n;
int m = x.size(), q = s.size();
for (int i = 0; i < m; ++i) {
if (x[i] < y[i]) swap(x[i], y[i]);
pre.add(x[i], y[i]);
suf.add(-y[i], -x[i]);
}
pre.build();
suf.build();
pre.dfs(n - 1, n - 1);
suf.dfs(0, 0);
vector<vector<int>> ps(n + 1);
for (int i = 0; i < n; ++i) {
ps[pre.tin[i]].push_back(suf.tin[i]);
}
vector<vector<Query>> qs(n + 1);
for (int i = 0; i < q; ++i) {
int u = pre.getR(e[i], r[i]), v = suf.getL(s[i], l[i]);
qs[pre.tin[u] - 1].push_back(Query(suf.tin[v], suf.tout[v], i, -1));
qs[pre.tout[u]].push_back(Query(suf.tin[v], suf.tout[v], i, 1));
}
for (int i = 0; i <= n; ++i) {
for (int p : ps[i]) {
add(p);
}
for (auto q : qs[i]) {
ans[q.id] += q.sgn * get(q.l, q.r);
}
}
for (int i = 0; i < q; ++i) ans[i] = ans[i] > 0;
return vector<int>(ans, ans + q);
}
