#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 2e5 + 7;
struct Query{
int s, e, l, r, x1, x2, y1, y2, ind;
};
struct DSU{
int root[N], pos[N];
vector<int> a[N];
void init(int n){
for(int i = 0; i < n; i++){
root[i] = i;
pos[i] = 0;
a[i].clear();
a[i].push_back(i);
}
}
int findRoot(int u){
if (u == root[u])
return u;
return root[u] = findRoot(root[u]);
}
int getL(int u){
int r = findRoot(u);
return pos[a[r].front()] - pos[u];
}
int getR(int u){
int r = findRoot(u);
return pos[a[r].back()] - pos[u];
}
void unite(int u, int v){
u = findRoot(u);
v = findRoot(v);
if (u == v)
return;
if (a[u].size() < a[v].size())
swap(u, v);
root[v] = u;
int sz = a[u].size();
for(int x : a[v]){
a[u].push_back(x);
pos[x] += sz;
}
a[v].clear();
}
} dsu;
struct SegmentTree{
int n;
vector<int> d[N * 4];
void build(int id, int l, int r, const vector<pair<int, int>> &p){
if (l == r){
d[id].push_back(p[l].second);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid, p);
build(id << 1 | 1, mid + 1, r, p);
d[id].resize(r - l + 1);
merge(d[id << 1].begin(), d[id << 1].end(), d[id << 1 | 1].begin(), d[id << 1 | 1].end(), d[id].begin());
}
int get(int id, int l, int r, int u, int v, int lo, int hi){
if (v < l || r < u)
return 0;
if (u <= l && r <= v){
return upper_bound(d[id].begin(), d[id].end(), hi) - lower_bound(d[id].begin(), d[id].end(), lo);
}
int mid = (l + r) >> 1;
return get(id << 1, l, mid, u, v, lo, hi) + get(id << 1 | 1, mid + 1, r, u, v, lo, hi);
}
int get(int x1, int x2, int y1, int y2){
return get(1, 0, n - 1, x1, x2, y1, y2);
}
void init(const vector<pair<int, int>> &p){
n = p.size();
build(1, 0, n - 1, p);
}
} st;
vector<int> adj[N];
vector<Query> queries;
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
for(int i = 0; i < (int) x.size(); i++){
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
int q = s.size();
vector<int> ordQuery(q), x1(q), x2(q), y1(q), y2(q);
vector<pair<int, int>> points(n);
for(int i = 0; i < q; i++)
ordQuery[i] = i;
sort(ordQuery.begin(), ordQuery.end(), [&](const int &a, const int &b){
return l[a] > l[b];
});
dsu.init(n);
int ptr = n;
for(int ind : ordQuery){
while (ptr >= l[ind]){
int u = ptr--;
for(int v : adj[u])
if (v >= u)
dsu.unite(u, v);
}
x1[ind] = dsu.getL(s[ind]);
x2[ind] = dsu.getR(s[ind]);
}
while (ptr >= 0){
int u = ptr--;
for(int v : adj[u])
if (v >= u)
dsu.unite(u, v);
}
for(int i = 0; i < q; i++){
x1[i] += dsu.pos[s[i]];
x2[i] += dsu.pos[s[i]];
}
for(int i = 0; i < n; i++)
points[i].first = dsu.pos[i];
sort(ordQuery.begin(), ordQuery.end(), [&](const int &a, const int &b){
return r[a] < r[b];
});
dsu.init(n);
ptr = 0;
for(int ind : ordQuery){
while (ptr <= r[ind]){
int u = ptr++;
for(int v : adj[u])
if (v <= u)
dsu.unite(u, v);
}
y1[ind] = dsu.getL(e[ind]);
y2[ind] = dsu.getR(e[ind]);
}
while (ptr < n){
int u = ptr++;
for(int v : adj[u])
if (v <= u)
dsu.unite(u, v);
}
for(int i = 0; i < q; i++){
y1[i] += dsu.pos[e[i]];
y2[i] += dsu.pos[e[i]];
}
for(int i = 0; i < n; i++)
points[i].second = dsu.pos[i];
sort(points.begin(), points.end());
st.init(points);
vector<int> answer(q);
for(int i = 0; i < q; i++)
answer[i] = (st.get(x1[i], x2[i], y1[i], y2[i]) > 0);
return answer;
}
