#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define ll int
ll n,m,q,f[200005],in1[200005],out1[200005],timedfs1,pos1[200005],in2[200005],out2[200005],timedfs2,st[200005][19][2],d1,d2,query1[200005],query2[200005],u,v,seg[800005];
vector<ll>a[200005],aa[200005];
struct node
{
ll a,b,c,d;
};
vector<node>query[200005];
vector<ll>ans;
ll check(ll i)
{
if(f[i]<0)
return i;
return f[i]=check(f[i]);
}
void connect(ll x,ll y,ll z)
{
if(x>y&&z==1)
swap(x,y);
if(x<y&&z==2)
swap(x,y);
f[x]+=f[y];
f[y]=x;
}
void dfs(ll x,ll pa)
{
st[x][0][0]=pa;
timedfs1++;
in1[x]=timedfs1;
pos1[timedfs1]=x;
for(ll it:aa[x])
if(it!=pa)
dfs(it,x);
out1[x]=timedfs1;
}
void dfs1(ll x,ll pa)
{
// cout<<x<<" "<<pa<<'\n';
st[x][0][1]=pa;
timedfs2++;
in2[x]=timedfs2;
for(ll it:aa[x])
if(it!=pa)
dfs1(it,x);
out2[x]=timedfs2;
}
void update(ll id,ll l,ll r,ll u,ll v)
{
if(l>u||r<u)return;
if(l==r)
{
seg[id]=v;
return;
}
ll mid=(l+r)/2;
update(id*2,l,mid,u,v);
update(id*2+1,mid+1,r,u,v);
seg[id]=max(seg[id*2],seg[id*2+1]);
}
ll getmax(ll id,ll l,ll r,ll u,ll v)
{
if(r<u||l>v)
return 0;
if(l>=u&&r<=v)
return seg[id];
ll mid=(l+r)/2;
return max(getmax(id*2,l,mid,u,v),getmax(id*2+1,mid+1,r,u,v));
}
vector<ll> check_validity(int N,vector<ll>X,vector<ll>Y,vector<ll>S,vector<ll>E,vector<ll>L,vector<ll>R)
{
n=N;
m=X.size();
q=S.size();
for(int i=0;i<m;i++)
{
a[X[i]+1].push_back(Y[i]+1);
a[Y[i]+1].push_back(X[i]+1);
}
for(int i=1;i<=n;i++)
f[i]=-1;
for(int i=n;i>=1;i--)
for(ll it:a[i])
if(it>i)
{
u=check(it);
v=check(i);
if(u!=v)
{
aa[v].push_back(u);
aa[u].push_back(v);
// cout<<u<<" "<<v<<'\n';
connect(u,v,1);
}
}
dfs(1,1);
for(int j=1;j<=18;j++)
for(int i=1;i<=n;i++)
st[i][j][0]=st[st[i][j-1][0]][j-1][0];
for(int i=0;i<q;i++)
{
d1=L[i]+1;
d2=S[i]+1;
for(int j=18;j>=0;j--)
if(st[d2][j][0]>=d1)
d2=st[d2][j][0];
query1[i+1]=d2;
}
for(int i=1;i<=n;i++)
{
f[i]=-1;
aa[i].clear();
}
for(int i=1;i<=n;i++)
for(ll it:a[i])
if(it<i)
{
u=check(it);
v=check(i);
if(u!=v)
{
aa[v].push_back(u);
aa[u].push_back(v);
// cout<<u<<" "<<v<<'\n';
connect(u,v,2);
}
}
dfs1(n,n);
for(int j=1;j<=18;j++)
for(int i=1;i<=n;i++)
st[i][j][1]=st[st[i][j-1][1]][j-1][1];
for(int i=0;i<q;i++)
{
d1=R[i]+1;
d2=E[i]+1;
for(int j=18;j>=0;j--)
if(st[d2][j][1]<=d1)
d2=st[d2][j][1];
query2[i+1]=d2;
// cout<<query1[i+1]<<" "<<query2[i+1]<<'\n';
}
// for(int i=1;i<=n;i++)
// {
// cout<<i<<" "<<in1[i]<<" "<<out1[i]<<'\n';
// cout<<i<<" "<<in2[i]<<" "<<out2[i]<<'\n';
// }
ans.resize(q);
for(int i=1;i<=q;i++)
{
// cout<<query1[i]<<" "<<query2[i]<<" "<<in2[query1[i]]<<" "<<out2[query1[i]]<<'\n';
query[out1[query1[i]]].push_back({in1[query1[i]],in2[query2[i]],out2[query2[i]],i-1});
}
for(int i=1;i<=n;i++)
{
// cout<<pos1[i]<<" "<<in2[pos1[i]]<<'\n';
update(1,1,n,in2[pos1[i]],i);
for(node it:query[i])
{
// cout<<i<<" "<<it.a<<" "<<it.b<<" "<<it.c<<" "<<it.d<<'\n';
d1=getmax(1,1,n,it.b,it.c);
if(d1>=it.a)
ans[it.d]=1;
}
}
// for(ll it:ans)
// cout<<it<<" ";
return ans;
}
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("nam.inp","r",stdin);
// freopen("nam.out","w",stdout);
// cin>>n>>m>>q;
// vector<ll>x,y,s,e,l,r;
// x.resize(m);
// y.resize(m);
// s.resize(q);
// e.resize(q);
// l.resize(q);
// r.resize(q);
// for(int i=0;i<m;i++)
// cin>>x[i];
// for(int i=0;i<m;i++)
// cin>>y[i];
// for(int i=0;i<q;i++)
// cin>>s[i];
// for(int i=0;i<q;i++)
// cin>>e[i];
// for(int i=0;i<q;i++)
// cin>>l[i];
// for(int i=0;i<q;i++)
// cin>>r[i];
// check_validity(n,x,y,s,e,l,r);
//}
