#include <bits/stdc++.h>
using namespace std;
const int MN = 4e5+5, LG = 20;
int ds[MN], p[MN], rep[MN], N, M, Q, i, j, vis[MN][2], nxt, sp[MN][LG], rev[MN], mp[MN], ans[MN];
struct edge{int x, y;}; vector<edge> ee;
vector<int> adj[MN];
int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}
pair<int,int> a[MN]; set<int> st[MN];
struct qur{int s, r, id;}; vector<qur> q;
void dfs(int n){
vis[n][0]=++nxt; rev[nxt]=n; mp[n]=nxt;
sp[n][0]=p[n];
for(auto v : adj[n])
dfs(v);
vis[n][1]=nxt;
}
int anc(int n,int h){
for(int i=LG-1;i>=0;i--){
if(sp[n][i]>=h) n=sp[n][i];
}
return n;
}
vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l,vector<int> r){
N = n; M = x.size(); Q = s.size();
for(i=0;i<M;i++) ee.push_back({x[i]+1,y[i]+1});
for(i=0;i<Q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
for(i=1;i<=N;i++) ds[i]=i,rep[i]=i;
for(i=0;i<ee.size();i++){if(ee[i].x<ee[i].y)swap(ee[i].x,ee[i].y);}
sort(ee.begin(),ee.end(),[](edge i,edge j){return i.y>j.y;});
for(auto v : ee){
if(fnd(v.x)!=fnd(v.y)){
int x = fnd(v.x), y = fnd(v.y);
if(rep[x]>rep[y]) swap(x,y);
adj[rep[x]].push_back(rep[y]);
ds[y] = x; p[y] = x;
}
}
dfs(1);
for(j=1;j<LG;j++){
for(i=1;i<=N;i++)
sp[i][j]=sp[sp[i][j-1]][j-1];
}
for(i=0;i<Q;i++){
int x = anc(e[i], l[i]);
a[i+1]={vis[x][0],vis[x][1]};
q.push_back({s[i],r[i],i+1});
}
sort(q.begin(),q.end(),[](qur i,qur j){return i.r<j.r;});
for(i=1;i<=N;i++) ds[i]=i,st[i].insert(i);
for(i=0;i<ee.size();i++) swap(ee[i].x,ee[i].y);
sort(ee.begin(),ee.end(),[](edge i,edge j){return i.y<j.y;});
i = 0;
for(auto v : ee){
while(i<q.size()&&q[i].r<v.y){
int x = fnd(mp[q[i].s]);
int id = q[i].id;
auto it = st[x].lower_bound(a[id].first);
if(it!=st[x].end()&&*it<=a[id].second) ans[id]=1;
i++;
}
if(fnd(mp[v.x])!=fnd(mp[v.y])){
int x = fnd(mp[v.x]), y = fnd(mp[v.y]);
if(st[x].size()>st[y].size()) swap(x,y);
for(auto v : st[x]) st[y].insert(v);
st[x].clear();
ds[x] = y;
}
}
while(i<q.size()){
int x = fnd(q[i].s);
int id = q[i].id;
auto it = st[x].lower_bound(a[id].first);
if(it!=st[x].end()&&*it<=a[id].second) ans[id]=1;
i++;
}
vector<int> res;
for(i=1;i<=Q;i++) res.push_back(ans[i]);
return res;
}
