#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e5 + 7;
const int N2 = 4e5 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const int BASE = 137;
const int szBL = 350;
struct Query {
int S, T, L, R;
};
struct Data {
int L, R, L2, R2;
};
int n, m, Q;
vector<int> ke[N];
Query qr[N];
vector<int> events[N];
///KRT
int root;
int ein[N2], eout[N2];
vector<int> adj[N2];
int S[N2], T[N2];
pii RangeS[N2], RangeT[N2];
int Ans[N];
int inS[N2];
vector<pii> events_in_T[N2];
struct Disjoin_set {
int nNode;
int lab[N2];
void init (int n) {
rep (i, 1, n) {
lab[i] = i;
}
nNode = n;
}
int Find (int u) {
return u == lab[u] ? u : lab[u] = Find(lab[u]);
}
void Join (int u, int v, int typ) {
u = Find(u);
v = Find(v);
if (u == v)
return;
++nNode;
if (typ == 1) {
adj[nNode].pb(v);
adj[nNode].pb(u);
}
lab[u] = lab[v] = lab[nNode] = nNode;
}
}DSU;
struct Fenwick_Tree {
int m;
int fen[N2];
void init (int n) {
m = n;
}
void update (int pos, int val) {
for (; pos <= m; pos += pos & -pos) fen[pos] += val;
}
int get (int pos) {
int res = 0;
for (;pos > 0; pos -= pos & -pos) res += fen[pos];
return res;
}
int get (int L, int R) {
return get(R) - get(L - 1);
}
}BIT;
vector<int> process () {
auto make_Tree = [&] (int typ) {
rep (i, 1, n) vector<int> ().swap(events[i]);
rep (i, 1, Q) {
if (typ == 1) events[qr[i].R].pb(i);
else events[qr[i].L].pb(i);
}
DSU.init(n);
rep (i, 1, 2 * n) vector<int> ().swap(adj[i]);
{
int u = typ == -1 ? n : 1;
while (u <= n && u >= 1) {
iter (&v, ke[u]) {
if ((typ == -1 && v >= u) || (typ == 1 && v <= u))
DSU.Join(u, v, 1);
}
u += typ;
}
}
root = DSU.Find(1);
int time_dfs = 0;
function<void(int, int)> pdfs = [&] (int u, int p) {
ein[u] = ++time_dfs;
if (typ == -1) S[ein[u]] = u;
else T[ein[u]] = u;
iter (&v, adj[u]) {
if (v != p) {
pdfs(v, u);
}
}
eout[u] = time_dfs;
};
pdfs(root, 0);
{
DSU.init(n);
int u = typ == -1 ? n : 1;
while (u <= n && u >= 1) {
iter (&v, ke[u]) {
if ((typ == -1 && v >= u) || (typ == 1 && v <= u))
DSU.Join(u, v, 0);
}
iter (&id, events[u]) {
int start = (typ == 1 ? qr[id].T : qr[id].S);
int Anc = DSU.Find(start);
if (typ == 1) RangeT[id] = {ein[Anc], eout[Anc]};
else RangeS[id] = {ein[Anc], eout[Anc]};
}
u += typ;
}
}
};
make_Tree(-1);
make_Tree(1);
// rep (i, 1, 2 * n) cout << S[i]<<" \n"[i == 2 *n];
// rep (i, 1, 2 * n) cout << T[i]<<" \n"[i == 2 *n];
// rep (i, 1, Q) cout << RangeS[i].fs <<","<<RangeS[i].se<<" "<<RangeT[i].fs <<","<<RangeT[i].se<<"\n";
///calc
rep (i, 1, 2 * n) if (S[i] <= n && S[i] >= 1) inS[S[i]] = i;
rep (i, 1, Q) {
events_in_T[RangeT[i].fs - 1].pb({i, -1});
events_in_T[RangeT[i].se].pb({i, 1});
}
BIT.init(2 * n);
rep (i, 1, 2 * n) {
if (T[i] <= n && T[i] >= 1) BIT.update(inS[T[i]], 1);
iter (&id, events_in_T[i]) {
int idx = id.fs, sign = id.se;
int L, R;
tie(L, R) = RangeS[idx];
Ans[idx] += sign * BIT.get(L, R);
}
}
vector<int> res;
rep (i, 1, Q) {
res.pb(Ans[i] > 0);
// cout << Ans[i]<<"\n";
}
return res;
}
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;
m = SZ(X);
rep (i, 1, m) {
int u = X[i - 1], v = Y[i - 1];
++u, ++v;
ke[u].pb(v);
ke[v].pb(u);
}
Q = SZ(_S);
rep (i, 1, Q) {
qr[i].S = _S[i - 1];
qr[i].T = _E[i - 1];
qr[i].L = _L[i - 1];
qr[i].R = _R[i - 1];
++qr[i].S, ++qr[i].T, ++qr[i].L, ++qr[i].R;
}
return process();
}
//#define file(name) if(fopen(name".inp","r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
//main () {
// vector<int> cur = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
// iter (&id, cur) cout << id <<"\n";
//// file("c");
// ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--) {
// process();
// }
//}
/*
onepunch +25
chắt lọc thông tin để mô hình
cận trên dưới
*/
