#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
//#define int long long
#define ld long double
#define pb push_back
const int N=3e5+5,M=317;
int n,q,m,cnt,par[2*N],vala[2*N],valb[2*N],sta[2*N],ena[2*N],stb[2*N],enb[2*N],spta[2*N][20],sptb[2*N][20],arra[2*N],arrb[2*N],upd[2*N],fenwick[2*N];
int ans[N];
struct query{
int u,val,i;
};
vector<query> event[2*N];
void update(int u){
while(u<2*n){
fenwick[u]++;
u+=(u&-u);
}
}
int get(int u){
int ans=0;
while(u){
ans+=fenwick[u];
u-=(u&-u);
}
return ans;
}
struct edge{
int val,u,v;
};
bool operator < (edge a,edge b){
return a.val<b.val;
}
bool operator > (edge a,edge b){
return a.val>b.val;
}
int Find(int u){
if(par[u]==u) return u;
else return par[u]=Find(par[u]);
}
vector<edge> vmin,vmax;
vector<int> adja[2*N],adjb[2*N];
void buildtreemin(int u,int v,int val){
u=Find(u); v=Find(v);
if(u==v) return;
cnt++; vala[cnt]=val;
par[u]=par[v]=cnt;
adja[cnt].push_back(u);
adja[cnt].push_back(v);
}
void buildtreemax(int u,int v,int val){
u=Find(u); v=Find(v);
if(u==v) return;
cnt++; valb[cnt]=val;
par[u]=par[v]=cnt;
adjb[cnt].push_back(u);
adjb[cnt].push_back(v);
}
void dfsa(int u){
sta[u]=++cnt;
arra[cnt]=u;
for(auto v:adja[u]){
spta[v][0]=u;
dfsa(v);
}
ena[u]=cnt;
}
void dfsb(int u){
stb[u]=++cnt;
arrb[cnt]=u;
for(auto v:adjb[u]){
sptb[v][0]=u;
dfsb(v);
}
enb[u]=cnt;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
m=x.size(); q=S.size();
for(int i=0;i<m;i++){
int u=x[i]+1,v=y[i]+1;
vmin.push_back({min(u,v),u,v});
vmax.push_back({max(u,v),u,v});
}
sort(vmin.begin(),vmin.end(),greater<edge>());
sort(vmax.begin(),vmax.end());
cnt=n;
for(int i=1;i<=n;i++) vala[i]=valb[i]=i;
for(int i=1;i<2*n;i++) par[i]=i;
for(auto i:vmin){
buildtreemin(i.u,i.v,i.val);
}
cnt=n;
for(int i=1;i<2*n;i++) par[i]=i;
for(auto i:vmax){
buildtreemax(i.u,i.v,i.val);
}
spta[2*n-1][0]=sptb[2*n-1][0]=2*n-1;
cnt=0;
dfsa(2*n-1);
cnt=0;
dfsb(2*n-1);
for(int j=1;j<20;j++){
for(int i=1;i<2*n;i++){
spta[i][j]=spta[spta[i][j-1]][j-1];
sptb[i][j]=sptb[sptb[i][j-1]][j-1];
}
}
for(int i=0;i<q;i++){
int s=S[i],e=E[i],l=L[i],r=R[i];
if(s<l || e>r) continue;
for(int i=19;i>=0;i--){
if(spta[s][i] != 0 && vala[spta[s][i]]>=l) s=spta[s][i];
}
for(int i=19;i>=0;i--){
if(sptb[e][i] != 0 && valb[sptb[e][i]]<=r) e=sptb[e][i];
}
event[ena[s]].push_back({enb[e],1,i});
event[sta[s]-1].push_back({enb[e],-1,i});
event[ena[s]].push_back({stb[e]-1,-1,i});
event[sta[s]-1].push_back({stb[e]-1,1,i});
}
for(int i=1;i<=n;i++){
upd[sta[i]]=stb[i];
}
for(int i=1;i<2*n;i++){
if(upd[i]){
update(upd[i]);
}
for(auto j:event[i]){
ans[j.i]+=get(j.u)*j.val;
}
}
vector<int> res;
for(int i=0;i<q;i++){
res.push_back((ans[i]!=0));
}
return res;
}
