#include<bits/stdc++.h>
using namespace std;
bool M1;
#define PI 3.14159265358979323846
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time cerr << "TIME : " << clock() * 0.001 << "s" <<'\n'
const int N=1e6+5,lg=30,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
return u+rd()%(v-u+1);
}
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,-1,0,1,1,-1,1,-1};
vector<int>ver[N],g[N];
int tin[N],tout[N],timer,tmp[N];
ii P[N];
iv val[N];
int r[N],n;
vector<int>req[N];
struct BIT
{
int n,z=0;
vector<int>bit,s;
BIT(){};
BIT(int _n):n(_n),bit(n+5,0),s(n+5,0),z(0){};
void check(int &idx){
if(s[idx]!=z){
bit[idx]=0;
s[idx]=z;
}
}
void update(int idx,int val){
while(idx<=n){
check(idx);
bit[idx]+=val;
idx+=idx&-idx;
}
}
int get(int idx){
int res=0;
while(idx>0){
check(idx);
res+=bit[idx];
idx-=idx&-idx;
}
return res;
}
void updaterange(int u,int v,int val){
update(u,val);
update(v+1,-val);
}
int getrange(int u,int v){
if(v<u)return 0;
return get(v)-get(u-1);
}
};
int acs(int u){
return r[u]==u?u:r[u]=acs(r[u]);
}
void join(int u,int v){
u=acs(u);
v=acs(v);
if(u==v)return;
++n;
r[u]=r[v]=r[n]=n;
g[n].emb(u);
g[n].emb(v);
}
void dfs(int u){
// cout <<u<<" ";
tin[u]=++timer;
// cout <<u<<" ";
for(auto v:g[u]){
dfs(v);
}
tout[u]=timer;
}
void process(int &node,vector<int> &S, vector<int> &E, vector<int>&L, vector<int> &R){
memset(r,-1,sizeof r);
for(int i=1;i<=node;++i)r[i]=i;
int query=sz(S);
for(int i=0;i<query;++i){
req[L[i]].emb(i);
}
n=node;
for(int i=node;i>=1;--i){
for(auto x:ver[i]){
if(x>i)join(i,x);
}
for(auto x:req[i]){
tmp[x]=acs(S[x]);
// cout <<acs(S[x])<<" ";
}
}
dfs(n);
for(int i=1;i<=node;++i)P[i].fi=tin[i];
for(int i=0;i<query;++i){
// cout <<tin[tmp[i]]<<" "<<tout[tmp[i]]<<'\n';
val[i].fi={tin[tmp[i]],tout[tmp[i]]};
}
}
void process1(int &node,vector<int> &S, vector<int> &E, vector<int>&L, vector<int> &R){
memset(r,-1,sizeof r);
for(int i=1;i<=node;++i)r[i]=i;
int query=sz(S);
for(int i=1;i<=n;++i){
req[i].clear();
g[i].clear();
}
for(int i=0;i<query;++i){
req[R[i]].emb(i);
}
n=node;
for(int i=1;i<=node;++i){
for(auto x:ver[i]){
if(x<i)join(i,x);
}
for(auto x:req[i]){
tmp[x]=acs(E[x]);
}
}
timer=0;
dfs(n);
// cout<<n<<'\n';
for(int i=1;i<=node;++i)P[i].se=tin[i];
for(int i=0;i<query;++i){
// cout <<tin[tmp[i]]<<" "<<tout[tmp[i]]<<'\n';
// cout <<tmp[i]<<" "<<tin[tmp[i]]<<" "<<tout[tmp[i]]<<'\n';
val[i].se={tin[tmp[i]],tout[tmp[i]]};
}
for(int i=1;i<=node;++i){
req[i].clear();
g[i].clear();
}
}
struct pt{
int d,c,i,t;
};
vector<pt>h[N];
bool M2;
vector<int> check_validity(int node, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int>L, vector<int> R){
for(int i=0;i<sz(X);++i){
++X[i];
++Y[i];
ver[X[i]].emb(Y[i]);
ver[Y[i]].emb(X[i]);
}
for(int i=0;i<sz(S);++i){
S[i]++;
E[i]++;
L[i]++;
R[i]++;
// cout <<S[i]<<" "<<E[i]<<" "<<L[i]<<" "<<R[i]<<'\n';
}
process(node,S,E,L,R);
process1(node,S,E,L,R);
int query=sz(S);
vector<int>ans(query);
for(int i=0;i<query;++i){
auto[x,y]=val[i];
h[x.fi-1].pb({y.fi,y.se,i,-1});
h[x.se].pb({y.fi,y.se,i,1});
// cout <<x.fi<<" "<<y.fi<<" "<<x.se<<" "<<y.se<<'\n';
}
BIT bit(n);
sort(P+1,P+1+node);
for(int i=1;i<=node;++i){
bit.update(P[i].se,1);
for(auto x:h[P[i].fi]){
// cout <<x.d<<" "<<x.t<<'\n';
// cout <<x.c<<" "<<x.t<<'\n';
ans[x.i]+=x.t*bit.getrange(x.d,x.c);
}
}
for(auto &x:ans)x=(x>0);
return ans;
}
// main()
// {
// srand(time(0));
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// #define task "aws"
// if(fopen(task".inp","r")){
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// int node,edge,query;
// cin >> node >> edge >> query;
// vector<int>x,y,s,e,l,r;
// for(int i=1;i<=edge;++i){
// int u,v;
// cin >> u >> v;
// x.emb(u);
// y.emb(v);
// // cout <<u<<" "<<v<<'\n';
// }
// for(int i=1;i<=query;++i){
// int st,ed,li,ri;
// cin >> st >> ed >> li >>ri;
// s.emb(st);
// e.emb(ed);
// l.emb(li);
// r.emb(ri);
// }
// vector<int>ans=check_validity(node,x,y,s,e,l,r);
// for(auto x:ans)cout << x<<'\n';
// look_memory;
// look_time;
// }
