#include "werewolf.h"
#include <bits/stdc++.h>
#define maxn 200010
#define loop(i, a, b) for(int i=a;i<b;i++)
#define cc(a) cout<< a << endl;
using namespace std;
struct seg{
map<int, map<int, bool>> tree;
void update(int x, int y){
x+=maxn;y+=maxn;
tree[x][y]=1;
for(int tx=x;tx>=1;tx>>=1){
for(int ty=y;ty>=1;ty>>=1) tree[tx][ty]=1;
}
}
bool query(int lx, int ly, int rx, int ry){
bool ret=0;
lx+=maxn;ly+=maxn;rx+=maxn;ry+=maxn;
int slx=lx; int srx=rx;
for(;slx<srx;slx>>=1, srx>>=1){
if(slx&1){
int sly=ly; int sry=ry;
for(;sly<sry;sly>>=1, sry>>=1){
if(sly&1) ret=ret or tree[slx][sly++];
if(sry&1) ret=ret or tree[slx][--sry];
}
slx++;
}
if(srx&1){
--srx;
int sly=ly; int sry=ry;
for(;sly<sry;sly>>=1, sry>>=1){
if(sly&1) ret=ret or tree[srx][sly++];
if(sry&1) ret=ret or tree[srx][--sry];
}
}
}
return ret;
}
};
vector<int> edges[maxn];
int pU[maxn];int pV[maxn];
vector<int> cU[maxn];vector<int> cV[maxn];
int fndU(int u){return (u==pU[u]) ? u:fndU(pU[u]);}
int fndV(int u){return (u==pV[u]) ? u:fndV(pV[u]);}
int sU[maxn];int eU[maxn];int sV[maxn];int eV[maxn];
int cntU=0;int cntV=0;
void dfsU(int u){
sU[u]=cntU;cntU++;
for(auto&& v:cU[u]) dfsU(v);
eU[u]=cntU;cntU++;
}
void dfsV(int u){
sV[u]=cntV;cntV++;
for(auto&& v:cV[u]) dfsV(v);
eV[u]=cntV;cntV++;
}
seg r;
int faU(int u, int m){
if (u==pU[u] or pU[u]>m) return u;
return faU(pU[u], m);
}
int faV(int u, int m){
if (u==pV[u] or pV[u]<m) return u;
return faV(pV[u], m);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) {
int M=X.size();int Q=S.size();
loop(i, 0, M){edges[X[i]].push_back(Y[i]);edges[Y[i]].push_back(X[i]);}
loop(i, 0, N) pU[i]=i;loop(i, 0, N) pV[i]=i;
loop(i, 0, N){
for(auto&& j: edges[i]){
if(j>i) continue;
int pj=fndU(j);
if(pj==i) continue;
pU[pj]=i;cU[i].push_back(pj);
}
}//disjoint union U
for(int i=N-1;i>=0;i--){
for(auto&& j: edges[i]){
if(j<i) continue;
int pj=fndV(j);
if(pj==i) continue;
pV[pj]=i;cV[i].push_back(pj);
}
}//disjoint union V
dfsU(N-1);dfsV(0);
loop(i, 0, N) r.update(sU[i], sV[i]);
vector<int> ans;ans.resize(Q);
loop(i, 0, Q){
int na=faV(S[i], L[i]);int nb=faU(E[i], R[i]);
ans[i]=r.query(sU[nb], sV[na], eU[nb], eV[na]);
}
return ans;
}
