#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef int64_t ll;
typedef int32_t ii;
//~ #define int ll
const int N = 2e5 + 5;
struct ST{
int tree[N << 2];
void set(int i, int v, int lx, int rx, int x){
if(lx == rx) { tree[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r){
return tree[x];
}
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
int get(int l, int r){
return get(l, r, 0, N, 1);
}
}tree;
const int M = 18;
vector<int> qwe[N], edges[2][N];
int tin[2][N], tout[2][N];
int par[2][N][M];
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
int m = x.size(), q = s.size();
for(int i=0;i<m;i++){
qwe[x[i]].push_back(y[i]);
qwe[y[i]].push_back(x[i]);
}
{ // building trees
vector<int> par(n), sz(n, 1), root(n);
iota(par.begin(), par.end(), 0);
iota(root.begin(), root.end(), 0);
function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
auto merge = [&](int a, int b, int r){
a = f(a), b = f(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a;
root[a] = r;
sz[a] += sz[b];
};
for(int i=n - 1;~i;i--){
for(auto x : qwe[i]){
if(x > i && root[f(x)] != i){
edges[0][i].push_back(root[f(x)]);
merge(x, i, i);
}
}
}
iota(par.begin(), par.end(), 0);
iota(root.begin(), root.end(), 0);
fill(sz.begin(), sz.end(), 1);
for(int i=0;i<n;i++){
for(auto x : qwe[i]){
if(x < i && root[f(x)] != i){
edges[1][i].push_back(root[f(x)]);
merge(x, i, i);
}
}
}
}
//~ for(int t=0;t<2;t++){
//~ for(int i=0;i<n;i++){
//~ for(auto x : edges[t][i]){
//~ cout<<t<<" "<<i<<" "<<x<<"\n";
//~ }
//~ }
//~ cout<<"\n";
//~ }
ar<int, 2> root = {0, n - 1};
for(int t=0;t<2;t++){
int t_ = 0;
function<void(int)> dfs = [&](int u){
for(int j=1;j<M;j++){
par[t][u][j] = par[t][par[t][u][j - 1]][j - 1];
}
tin[t][u] = ++t_;
for(auto x : edges[t][u]){
par[t][x][0] = u;
dfs(x);
}
tout[t][u] = t_;
};
par[t][root[t]][0] = root[t];
dfs(root[t]);
}
vector<ar<int, 2>> ver(n);
auto get = [&](int t, int u, int l, int r){
for(int j=M - 1;~j;j--){
if(l <= par[t][u][j] && par[t][u][j] <= r){
u = par[t][u][j];
}
}
return u;
};
for(int i=0;i<q;i++){
ver[i][0] = get(0, s[i], l[i], n);
ver[i][1] = get(1, e[i], 0, r[i]);
}
vector<int> p(q);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
return tout[0][ver[i][0]] < tout[0][ver[j][0]];
});
vector<int> tot(n);
iota(tot.begin(), tot.end(), 0);
sort(tot.begin(), tot.end(), [&](int i, int j){
return tout[0][i] < tout[0][j];
});
vector<int> res(q);
int j = 0;
for(auto i : p){
while(j < n && tin[0][tot[j]] <= tout[0][ver[i][0]]){
tree.set(tin[1][tot[j]], tin[0][tot[j]]);
j++;
}
if(tree.get(tin[1][ver[i][1]], tout[1][ver[i][1]]) >= tin[0][ver[i][0]]){
res[i] = 1;
}
}
return res;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
2 5
4 2 1 2
4 2 2 2
5 4 3 4
5 4 4
4 1
1 0
0 3
3 2
4 0 1 1
4 3 1 3
2 0 1 1
3 1 3 3
*/
