#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "werewolf.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e5 + 10;
vector <int> g[N];
int a[N];
struct DSU {
int n, ord[N];
int in[N], out[N];
int root[N];
vector <int> e[N];
DSU(int _n) {
n = _n;
for (int i = 0; i < n; ++i) root[i] = i;
}
int Find(int u) {
return (u == root[u] ? u : root[u] = Find(root[u]));
}
void Union(int u, int v) {
if ((u = Find(u)) == (v = Find(v))) return;
e[n].push_back(u);
e[n].push_back(v);
root[u] = n, root[v] = n;
root[n] = n;
++n;
}
int ti = 0;
void dfs(int u) {
if (e[u].size()) {
in[u] = 1e9, out[u] = - 1e9;
for (auto v: e[u]) dfs(v), in[u] = min(in[u], in[v]), out[u] = max(out[u], out[v]);
} else {
ord[ti] = u;
in[u] = out[u] = ti;
++ti;
}
}
void run() {
dfs(n - 1);
}
};
int node[N][2];
vector <pair <int, int> > QL[N], QR[N];
vector <int> st[N * 4];
void build(int id, int L, int R) {
if (L == R) {
st[id].push_back(a[L]);
return;
}
int mid = L + R >> 1;
build(id * 2, L, mid);
build(id * 2 + 1, mid + 1, R);
st[id].resize(R - L + 1);
merge(st[id * 2].begin(), st[id * 2].end(), st[id * 2 + 1].begin(), st[id * 2 + 1].end(), st[id].begin());
}
int get(int id, int L, int R, int u, int v, int x, int y) {
if (u > R || L > v) return 0;
if (u <= L && R <= v) {
auto iter = lower_bound(st[id].begin(), st[id].end(), x);
if (iter != st[id].end() && *iter <= y) return 1;
return 0;
}
int mid = L + R >> 1;
return get(id * 2, L, mid, u, v, x, y) || get(id * 2 + 1, mid + 1, R, u, v, x, y);
}
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();
int q = S.size();
for (int i = 0; i < m; ++i) {
int u = X[i], v = Y[i];
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> A(q);
for (int i = 0; i < q; ++i) {
int u = S[i], v = E[i], l = L[i], r = R[i];
QR[l].push_back({u, i});
QL[r].push_back({v, i});
}
DSU D1(n), D2(n);
for (int u = 0; u < n; ++u) {
for (auto v: g[u]) {
if (u > v) D1.Union(u, v);
}
for (auto [x, i]: QL[u]) node[i][0] = D1.Find(x);
}
for (int u = n - 1; u >= 0; --u) {
for (auto v: g[u]) {
if (u < v) D2.Union(u, v);
}
for (auto [x, i]: QR[u]) node[i][1] = D2.Find(x);
}
D1.run();
D2.run();
for (int i = 0; i < n; ++i) a[i] = D2.in[D1.ord[i]];
build(1, 0, n - 1);
for (int i = 0; i < q; ++i) {
A[i] = get(1, 0, n - 1, D1.in[node[i][0]], D1.out[node[i][0]], D2.in[node[i][1]], D2.out[node[i][1]]);
}
return A;
}
//namespace {
//
//int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
//}
//
//} // namespace
//
//int main() {
// int N = read_int();
// int M = read_int();
// int Q = read_int();
// std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
// for (int j = 0; j < M; ++j) {
// X[j] = read_int();
// Y[j] = read_int();
// }
// for (int i = 0; i < Q; ++i) {
// S[i] = read_int();
// E[i] = read_int();
// L[i] = read_int();
// R[i] = read_int();
// }
//
// std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
// for (size_t i = 0; i < A.size(); ++i) {
// printf("%d\n", A[i]);
// }
// return 0;
//}
