#include <bits/stdc++.h>
#include "werewolf.h"
#define ll long long
#define pb push_back
using namespace std;
const ll N = 3e5;
int n;
vector<int> g[N];
vector<int> nt[2][N];
struct DSU {
ll p[N] = {0};
ll get(ll v) {
return p[v] = (p[v] == v ? v : get(p[v]));
}
} rot[2];
ll tin[2][N], tout[2][N];
ll bp[2][N][20];
int arr[2][N];
void dfs(ll v, ll p, ll t) {
bp[t][v][0] = p;
tin[t][v] = ++tout[t][0];
arr[t][tin[t][v]] = v;
for(int j = 1; j < 20; j++)
bp[t][v][j] = bp[t][bp[t][v][j - 1]][j - 1];
for(auto u : nt[t][v]) {
dfs(u, v, t);
}
tout[t][v] = tout[t][0];
}
struct node {
node *l = nullptr, *r = nullptr;
ll sum = 0;
node() {};
} *rt[N];
void bld(node *v, ll l = 1, ll r = n) {
if(l == r)
return;
ll m = (l + r) >> 1ll;
v->l = new node();
v->r = new node();
bld(v->l, l, m);
bld(v->r, m + 1, r);
}
void upd(ll p, node *v, node *u, ll l = 1, ll r = n) {
if(l == r) {
v->sum = 1;
return;
}
ll m = (l + r) >> 1ll;
if(p <= m) {
v->r = u->r;
v->l = new node();
upd(p, v->l, u->l, l, m);
}
else {
v->l = u->l;
v->r = new node();
upd(p, v->r, u->r, m + 1, r);
}
v->sum = v->l->sum + v->r->sum;
}
ll get(ll l, ll r, node *v, ll tl = 1, ll tr = n) {
if(l > tr || tl > r)
return 0;
if(l <= tl && tr <= r)
return (v->sum);
ll m = (tl + tr) >> 1ll;
return get(l, r, v->l, tl, m) + get(l, r, v->r, m + 1, tr);
}
vector<int> check_validity(int NN, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
n = NN;
for(int i = 0; i < x.size(); i++) {
x[i]++, y[i]++;
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
}
for(int i = n; i >= 1; i--) {
rot[0].p[i] = i;
for(auto u : g[i]) {
if(u < i)continue;
ll z = rot[0].get(u);
if(z == i)continue;
nt[0][i].pb(z);
rot[0].p[z] = i;
}
}
for(int i = 1; i <= n; i++) {
rot[1].p[i] = i;
for(auto u : g[i]) {
if(u > i)continue;
ll z = rot[1].get(u);
if(z == i)continue;
nt[1][i].pb(z);
rot[1].p[z] = i;
}
}
dfs(1, 0, 0), dfs(n, 0, 1);
rt[0] = new node();
bld(rt[0]);
for(int i = 1; i <= n; i++) {
rt[i] = new node();
upd(tin[1][arr[0][i]], rt[i], rt[i - 1]);
}
vector<int> sub;
for(int i = 0; i < s.size(); i++) {
ll vs = s[i] + 1, ve = e[i] + 1;
ll L = l[i] + 1, R = r[i] + 1;
for(int j = 19; j >= 0; j--) {
if(bp[0][vs][j] >= L)
vs = bp[0][vs][j];
}
for(int j = 19; j >= 0; j--) {
if(bp[1][ve][j] && bp[1][ve][j] <= R)
ve = bp[1][ve][j];
}
ll l1 = tin[0][vs], r1 = tout[0][vs];
ll l2 = tin[1][ve], r2 = tout[1][ve];
ll h = get(l2, r2, rt[r1]) - get(l2, r2, rt[l1 - 1]);
sub.pb((h?1:0));
}
return sub;
}
/*
int main() {
int p, m, q;
cin >> p >> m >> q;
vector<int> x,y,l,r,s,e;
for(int i = 1; i <= m; i++) {
ll a, b;
cin >> a >> b;
x.pb(a),y.pb(b);
}
while(q--) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
l.pb(c), r.pb(d);
s.pb(a), e.pb(b);
}
vector<int> ans = check_validaty(p, x, y, s, e, l, r);
for(auto u : ans)
cout << u << " ";
} */
