#include <bits/stdc++.h>
using namespace std;
const int N = 200000, L = __lg(N) + 1;
struct segtree {
segtree *left, *right;
int maxi;
segtree(int l, int r) {
maxi = 0;
if (l < r) {
int m = (l + r) / 2;
left = new segtree(l, m);
right = new segtree(m + 1, r);
}
}
void update(int a, int x, int l, int r) {
if (l == r) {
maxi = x;
} else {
int m = (l + r) / 2;
if (a <= m) {
left->update(a, x, l, m);
} else {
right->update(a, x, m + 1, r);
}
maxi = max(left->maxi, right->maxi);
}
}
int query(int a, int b, int l, int r) {
if (b < l || r < a) {
return INT_MIN;
} else if (a <= l && r <= b) {
return maxi;
} else {
int m = (l + r) / 2;
return max(
left->query(a, b, l, m),
right->query(a, b, m + 1, r)
);
}
}
};
int in_l[N], out_l[N], par_l[L][N], in_r[N], out_r[N], par_r[L][N], t;
vector<int> tree_l[N], tree_r[N];
int dsu[N];
int find(int u) {
if (dsu[u] == -1) {
return u;
}
dsu[u] = find(dsu[u]);
return dsu[u];
}
void dfs(int u, vector<int> *adj, int *in, int *out, int *par) {
in[u] = ++t;
for (auto c : adj[u]) {
par[c] = u;
dfs(c, adj, in, out, par);
}
out[u] = t;
}
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 = x.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; ++i) {
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
fill(dsu, dsu + n, -1);
for (int i = 0; i < n; ++i) {
for (auto j : adj[i]) {
if (j < i && find(j) != i) {
tree_l[i].push_back(find(j));
dsu[find(j)] = i;
}
}
}
par_l[0][n - 1] = n - 1;
dfs(n - 1, tree_l, in_l, out_l, par_l[0]);
fill(dsu, dsu + n, -1);
for (int i = n - 1; i >= 0; --i) {
for (auto j : adj[i]) {
if (j > i && find(j) != i) {
tree_r[i].push_back(find(j));
dsu[find(j)] = i;
}
}
}
par_r[0][0] = 0;
dfs(0, tree_r, in_r, out_r, par_r[0]);
for (int i = 1; i <= __lg(n); ++i) {
for (int j = 0; j < n; ++j) {
par_l[i][j] = par_l[i - 1][par_l[i - 1][j]];
par_r[i][j] = par_r[i - 1][par_r[i - 1][j]];
}
}
int q = s.size();
vector<array<int, 3>> queries;
for (int i = 0; i < q; ++i) {
for (int j = __lg(n); j >= 0; --j) {
if (par_l[j][e[i]] <= r[i]) {
e[i] = par_l[j][e[i]];
}
if (par_r[j][s[i]] >= l[i]) {
s[i] = par_r[j][s[i]];
}
}
queries.push_back({out_r[s[i]], 1, i});
}
for (int i = 0; i < n; ++i) {
queries.push_back({in_r[i], 0, in_l[i]});
}
sort(queries.begin(), queries.end());
vector<int> ans(q);
segtree *maxi = new segtree(1, n);
for (auto [a, b, c] : queries) {
if (b == 0) {
maxi->update(c, a, 1, n);
} else {
ans[c] = maxi->query(in_l[e[c]], out_l[e[c]], 1, n) >= in_r[s[c]];
}
}
return ans;
}
