#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(), (x).end()
#define deb(x) cout << #x << "-" << x << endl
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef char chr;
typedef string str;
typedef long long ll;
typedef vector<int> vii;
typedef pair<int, int> pii;
const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const double PI = 2 * acos(0.0);
const int N = 2e5+5;
vector <vii> g(N),v(N);
int par[N];
int cur;
int in[N],out[N];
int x[N],y[N];
pii Lr[N],Rr[N];
int px[N],py[N];
int A[N];
vector <vii> t(N*4);
void cleardsu() {
for (int i = 0; i < N; i++) {
par[i] = i;
v[i].clear();
}
}
int getpar(int x) {
if (x == par[x]) return x;
return par[x] = getpar(par[x]);
}
void unionset(int a, int b) {
a = getpar(a);
b = getpar(b);
if (a == b) return;
par[a] = par[b];
v[a].pb(b);
v[b].pb(a);
}
void dfs(int x, int p) {
in[x] = ++cur;
for (auto to:v[x]) {
if (to == p) continue;
dfs(to,x);
}
out[x] = cur;
}
vii merge(vii a, vii b) {
vii res;
int pos1 = 0;
int pos2 = 0;
while (pos1 < sz(a) && pos2 < sz(b)) {
if (a[pos1] < b[pos2]) {
res.pb(a[pos1]);
pos1++;
} else {
res.pb(b[pos2]);
pos2++;
}
}
while (pos2 < sz(b)) {
res.pb(b[pos2]);
pos2++;
}
while (pos1 < sz(a)) {
res.pb(a[pos1]);
pos1++;
}
return res;
}
void build(int node, int l, int r) {
if (l == r) {
t[node].pb(A[l]);
return;
}
int mid = (l+r)/2;
build (node*2,l,mid);
build(node*2+1,mid+1,r);
t[node] = merge(t[node*2],t[node*2+1]);
}
bool getans(int node, int l, int r, int lx, int rx, int ly, int ry) {
if (r < lx || l > rx) return 0;
if (l >= lx && r <= rx) {
auto it = lower_bound(all(t[node]),ly);
return (it != t[node].end() && *it <= ry);
}
int mid = (l+r)/2;
return (getans(node*2,l,mid,lx,rx,ly,ry) || getans(node*2+1,mid+1,r,lx,rx,ly,ry));
}
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 Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
for (int i = 0; i < sz(X); i++) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
cleardsu();
for (int i = N-1; i >= 0; i--) {
unionset(N+i,i);
for (auto to: g[i]) {
if (to >= i) {
unionset(N+i,to);
}
}
}
dfs(N,N);
iota(x,x+N,0);
sort(x,x+N,[](int a, int b) {
return in[a]<in[b];
});
for (int i = 0; i < N; i++) {
int l = 0, r = N-1;
int tl=-1;
while (l <= r) {
int mid = (l+r)/2;
if (in[x[mid]] >= in[i+N]) {
r = mid - 1;
tl = mid;
} else {
l = mid + 1;
}
}
l = 0; r = N-1;
int tr = -1;
while (l <= r) {
int mid = (l+r)/2;
if (in[x[mid]] <= out[i+N]) {
l = mid + 1;
tr = mid;
} else {
r = mid - 1;
}
}
Lr[i] = mp(tl,tr);
}
cleardsu();
for (int i = 0; i < N; i++) {
for (auto to:g[i]) {
if (to <= i) {
unionset(N+i,to);
}
}
}
dfs(2*N-1,2*N-1);
iota(y,y+N,0);
sort(y,y+N,[](int a, int b) {
return in[a]<in[b];
});
for (int i = 0; i < N; i++) {
int l = 0, r = N-1;
int tl=-1;
while (l <= r) {
int mid = (l+r)/2;
if (in[y[mid]] >= in[i+N]) {
r = mid - 1;
tl = mid;
} else {
l = mid + 1;
}
}
l = 0; r = N-1;
int tr = -1;
while (l <= r) {
int mid = (l+r)/2;
if (in[y[mid]] <= out[i+N]) {
l = mid + 1;
tr = mid;
} else {
r = mid - 1;
}
}
Rr[i] = mp(tl,tr);
}
cleardsu();
for (int i = 0; i < N; i++) {
px[x[i]] = i;
}
for (int i = 0; i < N; i++) {
py[y[i]] = i;
}
for (int i = 0; i < N; i++) {
A[px[i]] = py[i];
}
build (1,0,N-1);
int q = 0;
while (q < sz(S)) {
auto [lx,rx] = Lr[L[q]];
auto [ly,ry] = Rr[R[q]];
if (S[q] < L[q] || E[q] > R[q]) {
A[q] = 0;
continue;
}
A[q] = getans(1,0,N-1,lx,rx,ly,ry);
}
return A;
}
