#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
const int maxn = 2e5+5;
struct dsu
{
vector<int> par;
dsu(int n = 0)
{
par.resize(n);
for(int i = 0; i< n; i++) par[i] = i;
}
int findset(int x)
{
if(x == par[x]) return x;
return par[x] = findset(par[x]);
}
};
dsu hum, wolf;
int n, m, q;
vector<int> adj[maxn];
struct tahm
{
int s, e, l, r, id;
int hum, wolf;
tahm(int s, int e, int l, int r, int id): s(s), e(e), l(l), r(r), id(id) {}
};
bool cmpl(tahm a, tahm b)
{
return a.l< b.l;
}
bool cmpr(tahm a, tahm b)
{
return a.r< b.r;
}
vector<tahm> kench;
vector<int> twolf[2*maxn];
vector<int> thum[2*maxn];
vector<int> pred;
int numb[maxn];
int lb[2*maxn];
int rb[2*maxn];
void dfs(int u = 2*n-2)
{
if(u< n) pred.pb(u);
for(int v : twolf[u]) dfs(v);
}
void calc(int u = 2*n-2)
{
lb[u] = 1e9, rb[u] = -1;
if(u< n) lb[u] = rb[u] = numb[u];
for(int v : twolf[u])
{
calc(v);
lb[u] = min(lb[u], lb[v]);
rb[u] = max(rb[u], rb[v]);
}
// printf("lb[%d] = %d, rb[%d] = %d\n", u, lb[u], u, rb[u]);
}
set<int> roots[2*maxn];
vector<int> elems[2*maxn];
vector<tahm> want[2*maxn];
vector<int> ans;
void comb(int u = 2*n-2)
{
if(u< n)
{
roots[u].insert(numb[u]);
elems[u].pb(numb[u]);
}
ii big = {0, -1};
for(int v : thum[u])
{
comb(v);
big = max(big, {(int) elems[v].size(), v});
}
if(big.Y != -1)
{
swap(roots[u], roots[big.Y]);
swap(elems[u], elems[big.Y]);
for(int v : thum[u])
{
for(int x : elems[v])
{
roots[u].insert(x);
elems[u].pb(x);
}
}
}
for(tahm kk : want[u])
{
int id = kk.id;
int wolf = kk.wolf;
int lo = lb[wolf], hi = rb[wolf];
ans[id] = roots[u].upper_bound(hi) != roots[u].upper_bound(lo-1);
}
}
vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R)
{
n = N;
m = X.size();
q = S.size();
for(int i = 0; i< q; i++) kench.pb(tahm(S[i], E[i], L[i], R[i], i));
for(int i = 0; i< m; i++)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
wolf = dsu(2*n);
sort(kench.begin(), kench.end(), cmpr);
int pt = 0;
int cnt = n;
for(int i = 0; i< n; i++)
{
for(int v : adj[i])
{
if(v< i)
{
int a = wolf.findset(i);
int b = wolf.findset(v);
if(a == b) continue;
wolf.par[a] = wolf.par[b] = cnt;
twolf[cnt].pb(a);
twolf[cnt].pb(b);
// printf("%d-->%d %d-->%d\n", cnt, a, cnt, b);
cnt++;
}
}
while(pt< q && kench[pt].r == i)
{
int e = kench[pt].e;
int pp = wolf.findset(e);
kench[pt].wolf = pp;
pt++;
}
}
// printf("finished wolf\n");
hum = dsu(2*n);
sort(kench.begin(), kench.end(), cmpl);
reverse(kench.begin(), kench.end());
pt = 0;
cnt = n;
for(int i = n-1; i>= 0; i--)
{
for(int v : adj[i])
{
if(v> i)
{
int a = hum.findset(v);
int b = hum.findset(i);
if(a == b) continue;
hum.par[a] = hum.par[b] = cnt;
// printf("%d->%d, %d->%d\n", cnt, a, cnt, b);
thum[cnt].pb(a);
thum[cnt].pb(b);
cnt++;
}
}
while(pt< q && kench[pt].l == i)
{
int s = kench[pt].s;
int pp = hum.findset(s);
kench[pt].hum = pp;
pt++;
}
}
dfs();
// for(int i = 0; i< n; i++) printf("%d ", pred[i]);
// printf("\n");
for(int i = 0; i< n; i++) numb[pred[i]] = i;
calc();
// printf("finished renumbering\n");
ans.resize(q);
for(int i = 0; i< q; i++)
{
int wolf = kench[i].wolf, hum = kench[i].hum;
want[kench[i].hum].pb(kench[i]);
}
comb();
// printf("%d\n", roots[2*n-2]->ask(0, n-1));
return ans;
}
