#include <cstdio>
#include <cstdlib>
#include <vector>
#define NN 200005
#define ll long long int
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;
ll ans=0,m,n,q,mark1[NN],mark2[NN];
vector<int> v[NN];
void f1(int ind,int mn)
{
if(mark1[ind])
return;
if(ind<mn)
return;
// printf("%d ", ind);
mark1[ind]=1;
for(int i=0;i<v[ind].size();i++)
{
ll x=v[ind][i];
if(!mark1[x] && x>=mn)
f1(x,mn);
}
}
void f2(int ind,int mk)
{
if(mark2[ind])
return;
if(ind>mk)
return;
if(mark1[ind])
ans=1;
// printf("%d ", ind);
mark2[ind]=1;
for(int i=0;i<v[ind].size();i++)
{
ll x=v[ind][i];
if(!mark2[x] && x<=mk)
f2(x,mk);
}
}
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) {
n=NN;
m=X.size();
q=S.size();
fo(i,0,m-1)
{
int a=X[i];
int b=Y[i];
v[a].pb(b);
v[b].pb(a);
}
std::vector<int> A(q);
for (int i = 0; i < q; ++i) {
fo(j,0,n-1)
mark1[j]=0,mark2[j]=0;
ans=0;
// printf("[d1] %d\n", i);
f1(S[i],L[i]);
printf("\n");
// printf("[d2] %d\n", i);
f2(E[i],R[i]);
// printf("\n\n");
A[i]=ans;
}
return A;
}
// 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;
// }
