#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int lim = 2e5 + 5;
int n, m, q;
vector<int>X, Y, S, E, L, R, g[lim];
namespace sub12{
vector<int>solve(){
vector<int>ans(q);
for(int i = 0; i < q; i++){
vector<vector<bool>>f(n + 1, vector<bool>(2, false));
queue<pair<int, int>>q;
q.emplace(S[i], 0);
f[S[i]][0] = true;
while(!q.empty()){
auto [s, c] = q.front();
q.pop();
if(c == 0 && L[i] <= s && R[i] >= s){
f[s][1] = true;
q.emplace(s, 1);
}
for(int& j : g[s]){
int d = s ^ X[j] ^ Y[j];
if(((c == 0 & d >= L[i]) || (c == 1 && d <= R[i])) && !f[d][c]){
f[d][c] = true;
q.emplace(d, c);
}
}
}
ans[i] = f[E[i]][1];
}
return ans;
}
}
namespace sub3{
bool check_subtask(){
if(m != n - 1){
return false;
}
for(int i = 1; i <= n; i++){
if(g[i].size() > 2){
return false;
}
}
return true;
}
vector<int>solve(){
int tdfs = 0;
vector<int>low(n + 1), low2v(n + 1), ans(q);
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
low2v[low[s] = ++tdfs] = s;
for(int& i : g[s]){
int d = X[i] ^ Y[i] ^ s;
if(d != p){
dfs(d, s);
}
}
};
for(int i = 1; i <= n; i++){
if(g[i].size() == 1){
dfs(i, -1);
break;
}
}
vector<pair<int, int>>st(n << 2 | 3);
auto merge = [&] (pair<int, int>a, pair<int, int>b){
return make_pair(min(a.first, b.first), max(a.second, b.second));
};
function<void(int, int, int)>build;
build = [&] (int id, int l, int r){
if(l == r){
st[id] = make_pair(low2v[l], low2v[l]);
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
};
build(1, 1, n);
function<int(int, int, int, int, int, const bool)>get;
get = [&] (int id, int l, int r, int u, int v, const bool is_min){
if(l > v || r < u){
return is_min ? INF : -INF;
}
if(u <= l && v >= r){
return is_min ? st[id].first : st[id].second;
}
int m = (l + r) >> 1, left = get(id << 1, l, m, u, v, is_min), right = get(id << 1 | 1, m + 1, r, u, v, is_min);
return is_min ? min(left, right) : max(left, right);
};
for(int i = 0; i < q; i++){
int s = low[S[i]], e = low[E[i]];
if(s < e){
int low = s + 1, high = e, ps = s, pe = e;
while(low <= high){
int mid = (low + high) >> 1;
if(get(1, 1, n, s, mid, true) >= L[i]){
low = (ps = mid) + 1;
}
else{
high = mid - 1;
}
}
low = s;
high = e - 1;
while(low <= high){
int mid = (low + high) >> 1;
if(get(1, 1, n, mid, e, false) <= R[i]){
high = (pe = mid) - 1;
}
else{
low = mid + 1;
}
}
ans[i] = pe <= ps;
}
else{
int low = e, high = s - 1, ps = s, pe = e;
while(low <= high){
int mid = (low + high) >> 1;
if(get(1, 1, n, mid, s, true) >= L[i]){
high = (ps = mid) - 1;
}
else{
low = mid + 1;
}
}
low = e + 1;
high = s;
while(low <= high){
int mid = (low + high) >> 1;
if(get(1, 1, n, e, mid, false) <= R[i]){
low = (pe = mid) + 1;
}
else{
high = mid - 1;
}
}
ans[i] = pe >= ps;
}
}
return ans;
}
}
namespace sub4{
int tdfs = 0, lab[lim], low[lim], tail[lim], bit[lim], up[18][lim];
vector<array<int, 3>>query[lim];
int find_set(int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
}
vector<int>krt[lim];
void dfs(int s){
low[s] = ++tdfs;
for(int& d : krt[s]){
if(d != up[0][s]){
up[0][d] = s;
dfs(d);
}
}
tail[s] = tdfs;
}
void update(int p){
for(; p <= n; p += p & -p){
bit[p]++;
}
}
int get(int p){
int ans = 0;
for(; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
vector<int>solve(){
iota(lab + 1, lab + n + 1, 1);
for(int i = n; i > 0; i--){
for(int& ie : g[i]){
int j = find_set(X[ie] ^ Y[ie] ^ i);
if(j > i){
krt[lab[j] = i].push_back(j);
}
}
}
memset(up[0], 0, sizeof(up[0]));
dfs(1);
for(int i = 1; i < 18; i++){
for(int j = 0; j <= n; j++){
up[i][j] = up[i - 1][up[i - 1][j]];
}
}
vector<pair<int, int>>tq1(q);
for(int i = 0; i < q; i++){
int x = S[i];
for(int j = 17; j > -1; j--){
int nx = up[j][x];
if(nx >= L[i]){
x = nx;
}
}
tq1[i] = make_pair(low[x], tail[x]);
}
vector<int>p1(n + 1);
for(int i = 1; i <= n; krt[i++].clear()){
p1[i] = low[i];
}
iota(lab + 1, lab + n + 1, 1);
for(int i = 1; i <= n; i++){
for(int& ie : g[i]){
int j = find_set(X[ie] ^ Y[ie] ^ i);
if(j < i){
krt[lab[j] = i].push_back(j);
}
}
}
memset(up[0], tdfs = 0, sizeof(up[0]));
dfs(n);
for(int i = 1; i < 18; i++){
for(int j = 1; j <= n; j++){
up[i][j] = up[i - 1][up[i - 1][j]];
}
}
for(int i = 1; i <= n; i++){
query[p1[i]].push_back({-1, low[i], -1});
}
for(int i = 0; i < q; i++){
int x = E[i];
for(int j = 17; j > -1; j--){
int nx = up[j][x];
if(nx != 0 && nx <= R[i]){
x = nx;
}
}
query[tq1[i].first - 1].push_back({low[x], tail[x], -i - 1});
query[tq1[i].second].push_back({low[x], tail[x], i});
}
vector<int>ans(q, 0);
memset(bit, 0, sizeof(bit));
for(int i = 1; i <= n; i++){
for(auto& [l, r, id] : query[i]){
if(l == -1){
update(r);
}
else if(id < 0){
ans[-id - 1] = get(r) - get(l - 1);
}
else{
ans[id] = get(r) - get(l - 1) > ans[id];
}
}
}
return ans;
}
}
vector<int>check_validity(int _n, vector<int>_X, vector<int>_Y, vector<int>_S, vector<int>_E, vector<int>_L, vector<int>_R){
swap(X, _X);
swap(Y, _Y);
swap(S, _S);
swap(E, _E);
swap(L, _L);
swap(R, _R);
m = X.size();
q = S.size();
for(int i = 0; i < m; i++){
g[++X[i]].emplace_back(i);
g[++Y[i]].emplace_back(i);
}
for(int i = 0; i < q; i++){
S[i]++;
E[i]++;
L[i]++;
R[i]++;
}
if((n = _n) <= 3000 && m <= 6000 && q <= 3000 && false){
return sub12::solve();
}
if(sub3::check_subtask() && false){
return sub3::solve();
}
return sub4::solve();
}
