#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
struct ST{
vector<int> t;
int n;
ST(int ns){
n = ns;
t.resize(4 * n);
}
int get(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2, vv = 2 * v;
return max(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
}
int get(int l, int r){
return get(1, 1, n, l, r);
}
void upd(int v, int tl, int tr, int& p, int& k){
if (tl == tr){
t[v] = k;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (p <= tm){
upd(vv, tl, tm, p, k);
}
else {
upd(vv + 1, tm + 1, tr, p, k);
}
t[v] = max(t[vv], t[vv + 1]);
}
void upd(int x, int y){
upd(1, 1, n, x, y);
}
};
struct dsu{
vector<vector<int>> g;
vector<int> p;
int n;
dsu(int ns){
n = ns;
p.resize(n + 1);
for (int i = 1; i <= n; i++){
p[i] = i;
}
tin.resize(n + 1);
tout.resize(n + 1);
g.resize(n + 1);
}
int get(int v){
if (p[v] != v){
p[v] = get(p[v]);
}
return p[v];
}
void unite(int x, int y){
x = get(x); y = get(y);
if (x == y) return;
p[y] = x;
g[x].pb(y);
}
vector<int> all = {0}, tin, tout;
int timer = 0;
void dfs(int v, int pr){
all.pb(v);
tin[v] = ++timer;
for (int i: g[v]){
if (i == pr) continue;
dfs(i, v);
}
tout[v] = timer;
}
};
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
int m = (int) x.size(), q = (int) s.size();
vector<int> g[n + 1];
for (int i = 0; i < m; i++){
x[i]++; y[i]++;
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
}
for (int i = 0; i < q; i++){
s[i]++; e[i]++;
l[i]++; r[i]++;
}
vector<int> d[n + 1], p1(q);
for (int i = 0; i < q; i++){
d[l[i]].pb(i);
}
dsu T1(n);
for (int i = n; i > 0; i--){
for (int j: g[i]){
if (j > i){
T1.unite(i, j);
}
}
for (int j: d[i]){
p1[j] = T1.get(s[j]);
}
}
for (int i = 1; i <= n; i++) d[i].clear();
for (int i = 0; i < q; i++){
d[r[i]].pb(i);
}
vector<int> p2(q);
dsu T2(n);
for (int i = 1; i <= n; i++){
for (int j: g[i]){
if (j < i){
T2.unite(i, j);
}
}
for (int j: d[i]){
p2[j] = T2.get(e[j]);
}
}
T1.dfs(1, 0);
T2.dfs(n, 0);
// Точки
vector<int> u(n + 1), v(n + 1);
for (int i = 1; i <= n; i++){
u[T1.all[i]] = i;
v[T2.all[i]] = i;
}
vector<int> st[n + 1];
for (int i = 1; i <= n; i++){
st[u[i]].pb(v[i]);
}
pair<pii, pii> rect[q];
for (int i = 0; i < q; i++){
rect[i] = {{T1.tin[p1[i]], T1.tout[p1[i]]}, {T2.tin[p2[i]], T2.tout[p2[i]]}};
}
vector<int> end[n + 1];
for (int i = 0; i < q; i++){
end[rect[i].ff.ss].pb(i);
}
vector<int> out(q);
ST T(n);
for (int i = 1; i <= n; i++){
for (int j: st[i]){
T.upd(j, i);
}
for (int j: end[i]){
out[j] = (T.get(rect[j].ss.ff, rect[j].ss.ss) >= rect[j].ff.ff);
}
}
return out;
}
