//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
// #include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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 M = SZ(X), Q = SZ(S);
if(M <= 10000 && Q <= 10000){
vector<int> g[N];
rep(i, 0, M){
int u = X[i], v = Y[i];
g[u].pb(v); g[v].pb(u);
}
vector<int> ans(Q);
rep(i, 0, Q){
int s = S[i], t = E[i], l = L[i], r = R[i];
int v = s;
queue<pii> q;
vector<vector<bool>> vis(2, vector<bool>(N, false));
q.push({s, 0}); vis[0][v] = true;
while(!q.empty()){
auto [v, k] = q.front();
q.pop();
if(k == 1 && v == t) break;
if(l <= v && v <= r && !vis[1][v]){
vis[1][v] = true;
q.push({v, 1});
}
for(int u : g[v]){
if(!k && u >= l){
if(!vis[k][u]){
vis[k][u] = true; q.push({u, k});
}
} else if(k && u <= r){
if(!vis[k][u]){
vis[k][u] = true; q.push({u, k});
}
}
}
}
ans[i] = (vis[1][t] == true);
}
return ans;
}
if(M == N - 1){
vector<int> g[N];
rep(i, 0, M){
int u = X[i], v = Y[i];
g[u].pb(v); g[v].pb(u);
}
vector<int> a, p(N);
rep(v, 0, N){
if(SZ(g[v]) == 1){
a.pb(v);
p[a.back()] = SZ(a) - 1;
while(SZ(a) < N){
v = a.back();
for(int u : g[v]){
if(SZ(a) == 1 || u != a[SZ(a) - 2]){
a.pb(u); p[a.back()] = SZ(a) - 1;
break;
}
}
}
break;
}
}
const int MAXK = 20;
int mnl[MAXK][N], mnr[MAXK][N], mxl[MAXK][N], mxr[MAXK][N];
rep(i, 0, N){
if(i > 0){
mnl[0][i] = min(a[i - 1], a[i]);
mxl[0][i] = max(a[i - 1], a[i]);
}
if(i < N - 1){
mnr[0][i] = min(a[i], a[i + 1]);
mxr[0][i] = max(a[i], a[i + 1]);
}
}
rep(k, 0, MAXK - 1){
rep(i, 0, N){
if(i + (1 << (k + 1)) < N){
mnr[k + 1][i] = min(mnr[k][i], mnr[k][i + (1 << k)]);
mxr[k + 1][i] = max(mxr[k][i], mxr[k][i + (1 << k)]);
}
if(i - (1 << (k + 1)) >= 0){
mnl[k + 1][i] = min(mnl[k][i], mnl[k][i - (1 << k)]);
mxl[k + 1][i] = max(mxl[k][i], mxl[k][i - (1 << k)]);
}
}
}
vector<int> ans(Q);
rep(i, 0, Q){
int s = S[i], t = E[i], l = L[i], r = R[i];
int ls = p[s], rs = p[s], lt = p[t], rt = p[t];
per(k, MAXK - 1, 0){
if(ls - (1 << k) >= 0 && mnl[k][ls] >= l){
ls -= (1 << k);
}
if(rs + (1 << k) < N && mnr[k][rs] >= l){
rs += (1 << k);
}
if(lt - (1 << k) >= 0 && mxl[k][lt] <= r){
lt -= (1 << k);
}
if(rt + (1 << k) < N && mxr[k][rt] <= r){
rt += (1 << k);
}
}
if(min(rs, rt) >= max(ls, lt)){
ans[i] = 1;
} else{
ans[i] = 0;
}
}
return ans;
}
}
