#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 200010;
pair <int, int> x_range[N], y_range[N];
vector <int> g[N], who[N], adj[N], t[N << 1];
int root[N], p[N], x_in[N], y_in[N], x_out[N], y_out[N], ptr, x_sub[N], y_sub[N];
int find (int x) {
return root[x] == x ? x : root[x] = find(root[x]);
}
void dfs (int* a, int *b, int u) {
a[u] = ptr++;
for (int v : adj[u]) dfs(a, b, v);
b[u] = ptr;
}
int query (int n, int l, int r, int lo, int hi) {
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
vector <int> &vec = t[l++];
int here = lower_bound(vec.begin(), vec.end(), hi) - lower_bound(vec.begin(), vec.end(), lo);
if (here) return 1;
}
if (r & 1) {
vector <int> &vec = t[--r];
int here = lower_bound(vec.begin(), vec.end(), hi) - lower_bound(vec.begin(), vec.end(), lo);
if (here) return 1;
}
}
return 0;
}
vector <int> solve (vector <pair <int, int>> pts, vector <tuple <int, int, int, int>> que) {
int n = pts.size(), q = que.size();
sort(pts.begin(), pts.end());
for (int i = 0; i < n; ++i) t[n + i] = {pts[i].second};
for (int i = n - 1; i; --i) merge(t[i << 1].begin(), t[i << 1].end(), t[i << 1 | 1].begin(), t[i << 1 | 1].end(), back_inserter(t[i]));
vector <int> ret;
for (auto &[l_x, r_x, l_y, r_y] : que) {
int l = lower_bound(pts.begin(), pts.end(), make_pair(l_x, -1)) - pts.begin();
int r = lower_bound(pts.begin(), pts.end(), make_pair(r_x, -1)) - pts.begin();
ret.emplace_back(query(n, l, r, l_y, r_y));
}
return ret;
}
vector <int> check_validity (int n, vector <int> ed_x, vector <int> ed_y, vector <int> que_s, vector <int> que_e, vector <int> que_l, vector <int> que_r) {
int m = ed_x.size(), q = que_s.size();
for (int i = 0; i < m; ++i) {
int u = ed_x[i], v = ed_y[i];
g[u].emplace_back(v);
g[v].emplace_back(u);
}
for (int i = 0; i < q; ++i) {
who[que_l[i]].emplace_back(i);
}
for (int i = 0; i < n; ++i) root[i] = i;
for (int i = n - 1; i >= 0; --i) {
set <int> childs;
for (int j : g[i]) if (j >= i) childs.emplace(find(j));
for (int j : childs) p[j] = root[j] = i;
for (int id : who[i]) x_sub[id] = find(que_s[id]);
}
for (int i = 1; i < n; ++i) adj[p[i]].emplace_back(i);
ptr = 0; dfs(x_in, x_out, 0);
for (int i = 0; i < n; ++i) who[i].clear(), adj[i].clear();
for (int i = 0; i < q; ++i) {
who[que_r[i]].emplace_back(i);
}
for (int i = 0; i < n; ++i) root[i] = i;
for (int i = 0; i < n; ++i) {
set <int> childs;
for (int j : g[i]) if (j <= i) childs.emplace(find(j));
for (int j : childs) p[j] = root[j] = i;
for (int id : who[i]) y_sub[id] = find(que_e[id]);
}
for (int i = 0; i < n - 1; ++i) adj[p[i]].emplace_back(i);
ptr = 0; dfs(y_in, y_out, n - 1);
vector <pair <int, int>> pts(n);
for (int i = 0; i < n; ++i) pts[i] = make_pair(x_in[i], y_in[i]);
vector <tuple <int, int, int, int>> que(q);
for (int i = 0; i < q; ++i) que[i] = make_tuple(x_in[x_sub[i]], x_out[x_sub[i]], y_in[y_sub[i]], y_out[y_sub[i]]);
return solve(pts, que);
}
