#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int p[2][200005][20];
int tp[2][200005];
int d[2][200005][20];
vector<int> adj[200005];
vector<int> child[2][200005];
int n ;
int find(int i, int id){
if(i == tp[id][i]){
return i;
}
return tp[id][i] = find(tp[id][i], id);
}
void build(int i, int id){
for(int x : adj[i]){
if((id == 0) ^ (x > i) == 1){
x = find(x, id);
if(x == i) continue;
p[id][x][0] = i;
tp[id][x] = i;
}
}
}
int cnt = 0;
int l[2][200005], r[2][200005];
int arr[2][200005];
int inv[200005];
void dfs(int v, int id){
if((id == 1 && v == 0) || (id == 0 && v == n - 1)){
} else {
d[id][v][0] = id == 0 ? max(v, p[id][v][0]) : min(v, p[id][v][0]);
for(int j = 1; j < 20; j++){
if(p[id][v][j - 1] == -1) break;
p[id][v][j] = p[id][p[id][v][j - 1]][j - 1];
d[id][v][j] = id == 0 ? max(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]) : min(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]);
}
}
l[id][v] = ++cnt;
arr[id][cnt] = v;
for(int x :child[id][v]){
dfs(x, id);
}
r[id][v] = cnt;
}
vector<int> seg[530000];
void builder(int id, int l, int r){
if(l == r){
seg[id].push_back(arr[0][l]);
return;
}
int m = (l + r) >> 1, id1 = id << 1, id2 = id << 1 | 1, it1 = 0, it2;
builder(id1, l, m);
builder(id2, m + 1, r);
int sz1 = seg[id1].size();
int sz2 = seg[id2].size();
while(it1 != sz1 && it2 != sz2){
if(seg[id1][it1] > seg[id2][it2])
seg[id].push_back(seg[id2][it2++]);
else
seg[id].push_back(seg[id1][it1++]);
}
while(it1 != sz1)
seg[id].push_back(seg[id1][it1++]);
while(it2 != sz2)
seg[id].push_back(seg[id2][it2++]);
}
bool query(int id, int l, int r, int L, int R, int D, int U){
if(r < L || l > R) return 0;
if(l >= L && r <= R){
return 0 != upper_bound(seg[id].begin(), seg[id].end(), U) - lower_bound(seg[id].begin(), seg[id].end(), D);
}
int m = (l + r) >> 1;
if(query(id << 1, l, m, L, R, D, U)) return 1;
if(query(id << 1 | 1, m + 1, r, L, R, D, U)) return 1;
return 0;
}
bool answer(int s, int e, int L, int R){
for(int i = 19; i >= 0; i--){
if(p[1][s][i] != -1 && d[1][s][i] >= L)
s = p[1][s][i];
if(p[0][e][i] != -1 && d[0][e][i] <= R)
e = p[0][e][i];
}
return query(1, 1, n, l[0][e], r[0][e], l[1][s], r[1][s]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
memset(p, -1, sizeof p);
for(int i = 0; i < N; i++){
tp[0][i] = tp[1][i] = i;
}
n = N;
for(int i = X.size() - 1; i >= 0; i--){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i++)
build(i, 0);
for(int i = N - 1; i >= 0; i--)
build(i, 1);
for(int i = 1; i < N; i++)
child[1][p[1][i][0]].push_back(i);
for(int i = N - 2; i >= 0; i--)
child[0][p[0][i][0]].push_back(i);
cnt = 0; dfs(0, 1);
cnt = 0; dfs(N - 1, 0);
for(int i = 1; i <= n; i++){
inv[arr[1][i]] = i;
}
for(int i = 1; i <= n; i++){
arr[0][i] = inv[arr[0][i]];
}
builder(1, 1, n);
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = answer(S[i], E[i], L[i], R[i]);
}
return A;
}
