#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N=200002;
typedef vector <int> vi;
typedef pair <int,int> pp;
int m,q,n;
vector <pp> pl[N],pr[N];
vector <int> A[N],vl[N],vr[N];
int dsu[N],gl[N],gr[N],fl[N],fr[N],x[N],y[N],rx[N],ry[N];
int type,dem;
int bit[N];
vector <int> res;
int root(int u)
{
while (dsu[u]>0) u=dsu[u];
return u;
}
void unionn(int u,int v)
{
if (dsu[u]>dsu[v]) swap(u,v);
dsu[u]+=dsu[v];dsu[v]=u;
if (type==0) vl[u].push_back(v);
else vr[u].push_back(v);
// cout<<type<<' '<<u<<' '<<v<<endl;
}
void dfsl(int u)
{
x[u]=++dem;
for (int v:vl[u])
{
if (x[v]>0) continue;
dfsl(v);
}
rx[u]=dem;
}
void dfsr(int u)
{
y[u]=++dem;
// cout<<u<<endl;
for (int v:vr[u])
{
if (y[v]>0) continue;
dfsr(v);
}
ry[u]=dem;
}
void build()
{
type=0;
for (int i=1;i<=n;i++)
dsu[i]=-1;
for (int i=1;i<=n;i++)
{
for (int v:A[i])
{
if (v>i) continue;
int a=root(i);int b=root(v);
if (a!=b) unionn(a,b);
}
for (int j=0;j<pl[i].size();j++)
{
int u=pl[i][j].first;
int pos=pl[i][j].second;
u=root(u);
fl[pos]=u;
gl[pos]=vl[u].size();
}
}
//for (int i=1;i<=n;i++)
// for (int j=1;j<=n;j++) assert(root(i)==root(j));
dem=0;dfsl(root(1));type=1;
for (int i=1;i<=n;i++)
dsu[i]=-1;
for (int i=n;i>=1;i--)
{
for (int v:A[i])
{
if (v<i) continue;
int a=root(i);int b=root(v);
if (a!=b) unionn(a,b);
}
for (int j=0;j<pr[i].size();j++)
{
int u=pr[i][j].first;
int pos=pr[i][j].second;
u=root(u);
fr[pos]=u;
gr[pos]=vr[u].size();
}
}
dem=0;dfsr(root(1));
}
void update(int i,int val)
{
for (i;i<=n;i+=i&(-i))
bit[i]+=val;
}
int get(int i)
{
int ans=0;
for (i;i>=1;i-=i&(-i))
ans+=bit[i];
return ans;
}
void solve_rec()
{
vector <int> X[N];
for (int i=1;i<=n;i++)
X[x[i]].push_back(y[i]);
vector <pair <pp,int> > Pl[N],Pr[N];
res.resize(q,0);
for (int i=0;i<q;i++)
{
int u=fl[i];
//if (gl[i]==0||gr[i]==0) continue;
int llx=x[u];int rrx=llx;if (gl[i]>0) rrx=rx[vl[u][gl[i]-1]];
u=fr[i];
int lly=y[u];int rry=lly;if (gr[i]>0) rry=ry[vr[u][gr[i]-1]];
Pl[llx-1].push_back({{lly,rry},i});
Pr[rrx].push_back({{lly,rry},i});
//cout<<i<<' '<<fl[i]<<' '<<gl[i]<<' '<<llx<<' '<<rrx<<' '<<lly<<' '<<rry<<endl;
}
// for (int i=1;i<=n;i++)
// cout<<x[i]<<' '<<y[i]<<endl;
for (int i=1;i<=n;i++)
{
for (int y:X[i]) update(y,1);
for (int j=0;j<Pl[i].size();j++)
{
int a=Pl[i][j].first.first;int b=Pl[i][j].first.second;
int pos=Pl[i][j].second;
res[pos]-=get(b)-get(a-1);
}
for (int j=0;j<Pr[i].size();j++)
{
int a=Pr[i][j].first.first;int b=Pr[i][j].first.second;
int pos=Pr[i][j].second;
res[pos]+=get(b)-get(a-1);
}
}
for (int i=0;i<q;i++)
res[i]=(res[i]>0);
}
vector <int> check_validity(int nn,vi X,vi Y,vi S,vi E,vi L,vi R)
{
n=nn;m=X.size();q=S.size();
for (int i=0;i<m;i++)
{
X[i]++;Y[i]++;
A[X[i]].push_back(Y[i]);
A[Y[i]].push_back(X[i]);
}
for (int i=0;i<q;i++)
{
S[i]++;E[i]++;L[i]++;R[i]++;
pl[R[i]].push_back({E[i],i});
pr[L[i]].push_back({S[i],i});
}
build();
solve_rec();
return res;
}
/*
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()
{
freopen("wereworf.inp","r",stdin);
freopen("wereworf.out","w",stdout);
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();
}
vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (int i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}
*/
