#include <bits/stdc++.h>
using namespace std ;
#define ll long long
// #define test
#ifndef test
#include "werewolf.h"
#endif
////////////////////////////////////////////////////////////////////////
vector <int> adj1[400003],adj2[400003] ;
int gp1[400003],gp2[400003] ;
int l1[400003],r1[400003] ;
int l2[400003],r2[400003] ;
int w1[400003],w2[400003] ;
int dsu1(int x){
if (x==gp1[x]) return x ;
gp1[x]=dsu1(gp1[x]) ;
return gp1[x] ;
}
int dsu2(int x){
if (x==gp2[x]) return x ;
gp2[x]=dsu2(gp2[x]) ;
return gp2[x] ;
}
int anc1[23][400003] ;
int anc2[23][400003] ;
int Cnt1=1,Cnt2=1 ;
int A[400003],B[400003] ;
void dfs1(int x){
l1[x]=r1[x]=Cnt1++ ;
A[l1[x]]=x ;
for (auto a : adj1[x]){
dfs1(a) ;
anc1[0][a]=x ;
r1[x]=r1[a] ;
}
}
void dfs2(int x){
l2[x]=r2[x]=Cnt2++ ;
B[l2[x]]=x ;
for (auto a : adj2[x]){
dfs2(a) ;
anc2[0][a]=x ;
r2[x]=r2[a] ;
}
}
int lift1(int x,int a){
for (int i = 20 ; i >= 0 ; i --){
if (w1[anc1[i][x]]<=a) x=anc1[i][x] ;
}
return x ;
}
int lift2(int x,int a){
for (int i = 20 ; i >= 0 ; i --){
if (w2[anc2[i][x]]>=a) x=anc2[i][x] ;
}
return x ;
}
struct SEGT {
int seg[1600003] ;
void build(){for (int i = 0 ; i < 1600003 ; i ++) seg[i]=INT_MAX/2 ;}
void upd(int id,int l,int r,int x,int v){
if (l==r&&l==x) seg[id]=v ;
else if (l>x||r<x) ;
else {
int md=(l+r)/2 ;
upd(id*2,l,md,x,v) ;
upd(id*2+1,md+1,r,x,v) ;
seg[id]=min(seg[id*2],seg[id*2+1]) ;
}
}
int qq(int id,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr) return seg[id] ;
else if (l>qr||r<ql) return INT_MAX/2 ;
else {
int md=(l+r)/2 ;
return min(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
}
}
} sgt ;
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();
std::vector<int> AA(Q,0);
int i,j ;
for (i = 0 ; i < 400003 ; i ++) gp1[i]=gp2[i]=w1[i]=w2[i]=i ;
vector <tuple<int,int,int>> ed1,ed2 ;
for (i = 0 ; i < M ; i ++){
ed1.push_back({max(X[i],Y[i]),X[i],Y[i]}) ;
ed2.push_back({min(X[i],Y[i]),X[i],Y[i]}) ;
}
sort(ed1.begin(),ed1.end()) ;
sort(ed2.begin(),ed2.end(),greater<tuple<int,int,int>>()) ;
int cnt1=N,cnt2=N ;
for (auto [c,a,b] : ed1){
a=dsu1(a),b=dsu1(b) ;
if (a!=b){
w1[cnt1]=c ;
adj1[cnt1].push_back(a) ;
adj1[cnt1].push_back(b) ;
gp1[a]=cnt1 ;
gp1[b]=cnt1 ;
cnt1++ ;
}
}
for (auto [c,a,b] : ed2){
a=dsu2(a),b=dsu2(b) ;
if (a!=b){
w2[cnt2]=c ;
adj2[cnt2].push_back(a) ;
adj2[cnt2].push_back(b) ;
gp2[a]=cnt2 ;
gp2[b]=cnt2 ;
cnt2++ ;
}
}
anc1[0][cnt1-1]=cnt1-1 ;
anc2[0][cnt2-1]=cnt2-1 ;
dfs1(cnt1-1) ;
dfs2(cnt2-1) ;
for (int k = 1 ; k <= 20 ; k ++){
for (i = 0 ; i < cnt1 ; i ++) anc1[k][i]=anc1[k-1][anc1[k-1][i]] ;
for (i = 0 ; i < cnt2 ; i ++) anc2[k][i]=anc2[k-1][anc2[k-1][i]] ;
}
vector <tuple<int,int,int,int>> qs[400003] ;
for (i = 0 ; i < Q ; i ++){
int x1=lift1(E[i],R[i]) ;
int x2=lift2(S[i],L[i]) ;
// for (j = l1[x1] ; j <= r1[x1] ; j ++) cout << A[j] << " " ; cout << endl ;
// for (j = l2[x2] ; j <= r2[x2] ; j ++) cout << B[j] << " " ; cout << endl ;
qs[l2[x2]].push_back({i,l1[x1],r1[x1],r2[x2]}) ;
}
sgt.build() ;
Cnt1--,Cnt2-- ;
for (i = 1 ; i <= Cnt2 ; i ++){
if (B[i]<N) sgt.upd(1,1,Cnt1,l1[B[i]],i) ;
}
for (i = 1 ; i <= Cnt2 ; i ++){
for (auto [id,L1,R1,R2] : qs[i]){
if (sgt.qq(1,1,Cnt1,L1,R1)<=R2) AA[id]=1 ;
}
if (B[i]<N) sgt.upd(1,1,Cnt1,l1[B[i]],INT_MAX/2) ;
}
// sort(qs.begin(),qs.end(),comp) ;
return AA;
}
////////////////////////////////////////////////////////////////////////
#ifdef test
//grader{
#include <cstdio>
#include <cstdlib>
#include <vector>
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}
//grader}
#endif
