#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int len = 2e5+5, lg = 18;
int ord[2][len], par[2][len], st[2][len], en[2][len], dp[2][lg][len];
int anc[len], cnt;
vector<int> adj[2][len], nex[len];
struct node{
int sum;
node *lef, *rig;
node(int s = 0, node *l = NULL, node *r = NULL){
sum = s;
lef = l;
rig = r;
}
};
typedef node* pnode;
pnode null = new node(), root[len];
pnode upd(pnode t, int l, int r, int i){
if (l == r)
return new node(t->sum+1, null, null);
int mid = (l+r)/2;
if (i <= mid)
return new node(t->sum+1, upd(t->lef, l, mid, i), t->rig);
return new node(t->sum+1, t->lef, upd(t->rig, mid+1, r, i));
}
int ask(pnode a, pnode b, int l, int r, int i, int j){
if (r < i || j < l)
return 0;
if (i <= l && r <= j)
return (a->sum-b->sum);
int mid = (l+r)/2;
return ask(a->lef, b->lef, l, mid, i, j) + ask(a->rig, b->rig, mid+1, r, i, j);
}
int fin(int i){
if (anc[i] == i) return i;
return anc[i] = fin(anc[i]);
}
void dfs(int u, int t){
ord[t][++cnt] = u;
st[t][u] = cnt;
for (int j = 0; j < adj[t][u].size(); j++){
int v = adj[t][u][j];
dfs(v, t);
par[t][v] = u;
}
en[t][u] = cnt;
}
ii sub(int u, int x, int t){
if (t == 0){
for (int j = lg-1; j >= 0; j--)
if (dp[t][j][u] > 0 && dp[t][j][u] >= x)
u = dp[t][j][u];
}
else{
for (int j = lg-1; j >= 0; j--)
if (dp[t][j][u] > 0 && dp[t][j][u] <= x)
u = dp[t][j][u];
}
return mp(st[t][u], en[t][u]);
}
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++){
int a = X[i]+1, b = Y[i]+1;
if (a > b)
swap(a, b);
nex[a].pb(b);
nex[b].pb(a);
}
for (int i = 1; i <= n; i++)
anc[i] = i;
for (int l = n; l >= 1; l--){
for (int j = 0; j < nex[l].size(); j++){
int v = nex[l][j];
if (l <= v && fin(v) != l)
adj[0][l].pb(fin(v)), anc[fin(v)] = l;
}
}
//for (int i = 1; i <= n; i++)
// printf("i = %d, fin = %d\n", i, fin(i));
for (int i = 1; i <= n; i++)
anc[i] = i;
for (int r = 1; r <= n; r++){
for (int j = 0; j < nex[r].size(); j++){
int v = nex[r][j];
if (r >= v && fin(v) != r)
adj[1][r].pb(fin(v)), anc[fin(v)] = r;
}
}
cnt = 0, dfs(1, 0);
cnt = 0, dfs(n, 1);
/*printf("ord0 =\n");
for (int i = 1; i <= n; i++)
printf("%d ", ord[0][i]);
printf("\n");
printf("ord1 =\n");
for (int i = 1; i <= n; i++)
printf("%d ", ord[1][i]);
printf("\n");*/
root[0] = null->lef = null->rig = null;
for (int i = 1; i <= n; i++)
root[i] = upd(root[i-1], 1, n, st[0][ord[1][i]]);
for (int t = 0; t < 2; t++)
for (int i = 1; i <= n; i++)
dp[t][0][i] = par[t][i];
for (int t = 0; t < 2; t++)
for (int j = 1; (1<<j) < n; j++)
for (int i = 1; i <= n; i++)
if (dp[t][j-1][i])
dp[t][j][i] = dp[t][j-1][dp[t][j-1][i]];
vector<int> out;
for (int i = 0; i < q; i++){
int s = S[i]+1, t = E[i]+1, l = L[i]+1, r = R[i]+1;
ii ra0 = sub(s, l, 0), ra1 = sub(t, r, 1);
if (ask(root[ra1.se], root[ra1.fi-1], 1, n, ra0.fi, ra0.se) > 0)
out.pb(1);
else
out.pb(0);
}
return out;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
