#include "werewolf.h"
#include <bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 11;
int N, Q, M;
int P[MAXN], sz, par[MAXN], val[MAXN], go[MAXN][2];
int getP(int a) {
if (a == P[a]) return a;
return P[a] = getP(P[a]);
}
vector<int>g[MAXN];
int L[MAXN], R[MAXN];
vector<int>G[2];
const int LOG = 20;
int up[MAXN][LOG];
void dfs(int v, int t) {
if (up[v][0] == 0) up[v][0] = v;
for (int i = 1 ; i < LOG ; ++ i) up[v][i] = up[up[v][i - 1]][i - 1];
if (!go[v][0] && !go[v][1]) {
L[v] = R[v] = G[t].size();
cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
G[t].emplace_back(v);
return;
}
up[go[v][0]][0] = up[go[v][1]][0] = v;
dfs(go[v][0], t);
dfs(go[v][1], t);
L[v] = L[go[v][0]];
R[v] = R[go[v][1]];
cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
}
vector<int>tv[MAXN << 2];
void build(int l = 0, int r = N, int v = 1) {
if (r - l == 1) {
tv[v] = {G[0][l]};
return;
}
int m = (l + r) >> 1;
build(l, m, v << 1), build(m, r, v<<1|1);
tv[v].resize(r - l);
merge(tv[v << 1].begin(), tv[v << 1].end(), tv[v<<1|1].begin(), tv[v<<1|1].end(),
tv[v].begin());
}
bool get(int L, int R, int x, int y, int l = 0, int r = N, int v = 1) {
if (L >= r || l >= R) return 0;
if (L <= l && r <= R) {
if (tv[v].back() < x) return 0;
return *lower_bound(tv[v].begin(), tv[v].end(), x) <= y;
}
int m = (l + r) >> 1;
if (get(L, R, x, y, l, m, v << 1)) return 1;
if (get(L, R, x, y, m, r, v<<1|1)) return 1;
return 0;
}
vector<int> check_validity(int N_, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> Lq, vector<int> Rq) {
N = N_;
M = X.size();
Q = S.size();
for (int i = 0 ; i < M ; ++ i) {
g[X[i]].emplace_back(Y[i]);
g[Y[i]].emplace_back(X[i]);
}
sz = N;
for (int i = 0 ; i < N ; ++ i) P[i] = i;
for (int i = 0 ; i < N ; ++ i) {
for (int j : g[i]) if (j < i) {
int x = getP(i);
int y = getP(j);
if (x != y) {
P[x] = P[y] = P[sz] = sz;
go[sz][0] = x, go[sz][1] = y;
par[x] = par[y] = sz;
val[sz] = i;
sz++;
}
}
}
dfs(sz-1, 0);
int off = sz;
for (int i = 0 ; i < N ; ++ i) P[i+off] = i+off;
sz += N;
for (int i = N-1 ; i >= 0 ; -- i) {
for (int j : g[i]) if (j > i) {
int x = getP(i+off);
int y = getP(j+off);
if (x != y) {
P[x] = P[y] = P[sz] = sz;
go[sz][0] = x, go[sz][1] = y;
par[x] = par[y] = sz;
val[sz] = i;
sz++;
}
}
}
dfs(sz-1, 1);
for (int &i : G[1]) i -= off;
for (int i : G[0]) cerr << i << " ";
cerr << ": G[0]\n";
for (int i : G[1]) cerr << i << " ";
cerr << ": G[1]\n";
vector<int>id(N);
for (int i = 0 ; i < N ; ++ i) {
id[G[1][i]] = i;
G[1][i] = i;
}
for (int i = 0 ; i < N ; ++ i) {
G[0][i] = id[G[0][i]];
}
for (int i : G[0]) cerr << i << " ";
cerr << ": G[0]\n";
for (int i : G[1]) cerr << i << " ";
cerr << ": G[1]\n";
build();
vector<int>ANS(Q);
for (int q = 0 ; q < Q ; ++ q) {
int Ls, Rs, Le, Re;
{
int v = E[q];
for (int i = LOG - 1 ; i >= 0 ; -- i) {
if (val[up[v][i]] <= Rq[q]) v = up[v][i];
}
Le = L[v], Re = R[v];
}
{
int v = S[q] + off;
for (int i = LOG - 1 ; i >= 0 ; -- i) {
if (val[up[v][i]] >= Lq[q]) v = up[v][i];
}
Ls = L[v], Rs = R[v];
}
cerr << Ls << " " << Rs << " " << Le << " " << Re << " LR" << endl;
bool has = false;
for (int i = Le ; i <= Re ; ++ i) {
for (int j = Ls ; j <= Rs ; ++ j) {
if (G[0][i] == G[1][j]) {
has = true;
}
}
}
ANS[q] = get(Le, Re + 1, Ls, Rs);
}
return ANS;
}
