#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
using vi = vector<int>;
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
template <typename T>
ostream& operator<<(ostream& out, const vector<T> &arr) {
for (int i = 0; i < sz(arr); i++) {
if (i) {
out << " ";
}
out << arr[i];
}
return out;
}
struct DSU {
vector<int> p;
DSU(int n) : p(n, -1) {}
int find(int u) {
return p[u] < 0 ? u : find(p[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
p[u] = v;
}
}
};
struct Tree {
int n;
vector<int> ord;
vector<pair<int, int>> ranges;
vector<vector<int>> lift, graph;
Tree(const vector<int>& p)
: n(sz(p)), ranges(n), lift(__lg(n) + 2, vector<int>(n)), graph(n) {
vector<int> roots;
for (int i = 0; i < n; i++) {
if (p[i] >= 0) {
graph[p[i]].push_back(i);
} else {
roots.push_back(i);
}
}
for (auto& a : roots) {
dfs(a);
}
lift[0] = p;
for (int i = 0; i <= __lg(n); i++) {
for (int j = 0; j < n; j++) {
if (lift[i][j] == -1) {
lift[i + 1][j] = -1;
} else {
lift[i + 1][j] = lift[i][lift[i][j]];
}
}
}
}
void dfs(int u) {
ranges[u].first = sz(ord);
ord.push_back(u);
for (auto& v : graph[u]) {
dfs(v);
}
ranges[u].second = sz(ord);
}
template <typename T>
pair<int, int> bsearch(int u, const T& t) {
for (int i = __lg(n); i >= 0; i--) {
int v = lift[i][u];
if (v != -1 && t(v)) {
u = v;
}
}
return ranges[u];
}
};
vector<int> solve(const vector<int>& arr1,
const vector<int>& arr2,
const vector<array<int, 4>>& queries) {
int n = sz(arr1), q = sz(queries);
assert(sz(arr1) == sz(arr2));
vector<int> ans(q);
for (int qi = 0; qi < q; qi++) {
auto& [l1, r1, l2, r2] = queries[qi];
bool vis[n] {};
for (int i = l1; i < r1; i++) {
vis[arr1[i]] = true;
}
for (int i = l2; i < r2; i++) {
ans[qi] |= vis[arr2[i]];
}
}
return ans;
}
vi check_validity(int n, vi us, vi vs, vi qsrc, vi qdest, vi ql, vi qr) {
int q = sz(qsrc);
vector<int> graph[n];
for (int i = 0; i < sz(us); i++) {
graph[us[i]].push_back(vs[i]);
graph[vs[i]].push_back(us[i]);
}
DSU inc(n), dec(n);
for (int i = 0; i < n; i++) {
for (auto& a : graph[i]) {
if (a <= i) {
inc.merge(a, i);
}
}
}
for (int i = n - 1; i >= 0; i--) {
for (auto& a : graph[i]) {
if (a >= i) {
dec.merge(a, i);
}
}
}
Tree inct(inc.p), dect(dec.p);
dbg(inc.p, dec.p);
vector<array<int, 4>> queries(q);
dbg(inct.ord, dect.ord);
for (int qi = 0; qi < q; qi++) {
int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi];
auto [il, ir] = inct.bsearch(dest, [&](int x) -> bool {
return x <= r;
});
auto [dl, dr] = dect.bsearch(src, [&](int x) -> bool {
return x >= l;
});
dbg(il, ir, dl, dr);
queries[qi] = {il, ir, dl, dr};
}
return solve(inct.ord, dect.ord, queries);
}
