#include <bits/stdc++.h>
using namespace std;
// #include "werewolf.h"
typedef vector<int> vi;
const int NL = 2e5, ML = 6e5, LOG = 21;
int N, M, Q, k, dfsTimer;
int e[NL], r[NL], p[2][LOG][ML], st[2*NL], tL[2][ML], tR[2][ML];
vi g[ML];
int find(int u){
return e[u] < 0 ? u : e[u] = find(e[u]);
}
void dfs(int u){
tL[k][u] = u < N ? ++dfsTimer : 1+dfsTimer;
for(int v : g[u]) dfs(v);
tR[k][u] = dfsTimer;
}
vi check_validity(int __N, vi X, vi Y, vi S, vi E, vi L, vi R){
N = __N, Q = size(S), M = size(X);
for(int i=0; i<M; ++i)
if(X[i] > Y[i]) swap(X[i], Y[i]);
vi h(M);
iota(begin(h), end(h), 0);
for(; k<2; ++k){
sort(begin(h), end(h), [&](int &u, int &v){
return k ? X[u] > X[v] : Y[u] < Y[v];
});
iota(r, r+N, 0);
fill(e, e+N,-1);
for(int &i : h){
int u = find(X[i]), v = find(Y[i]);
p[k][0][r[u]] = i+N;
p[k][0][r[v]] = i+N;
if(e[u] > e[v]) swap(u, v);
g[i+N] = {r[u]};
if(u != v) g[i+N].push_back(r[v]);
if(u != v){
e[u] += e[v];
e[v] = u;
}
r[u] = i+N;
}
dfsTimer = -1;
dfs(p[k][0][h.back()+N] = h.back()+N);
for(int i=0; i+1<LOG; ++i)
for(int u=0; u<N+M; ++u)
p[k][i+1][u] = p[k][i][p[k][i][u]];
}
vector<array<int, 3>> q(Q);
for(int i=0; i<Q; ++i){
int u = E[i];
for(int j=LOG; --j>=0; )
if(Y[p[0][j][u] - N] <= R[i]) u = p[0][j][u];
q[i] = {tL[0][u], tR[0][u], i};
}
vi byL(N), res(Q); int pt = N-1;
iota(begin(byL), end(byL), 0);
sort(begin(byL), end(byL), [&](int u, int v){
return tL[0][u] < tL[0][v];
});
sort(rbegin(q), rend(q));
fill(st, st+N+N, ML);
for(auto &[lx, rx, id] : q){
while(pt>=0 && tL[0][byL[pt]] >= lx){
int i = tL[1][byL[pt]];
for(st[i+=N]=tL[0][byL[pt]]; i/=2; )
st[i] = min(st[2*i], st[2*i+1]);
--pt;
}
int u = S[id];
for(int j=LOG; --j>=0; )
if(X[p[1][j][u] - N] >= L[id]) u = p[1][j][u];
int qL = tL[1][u], qR = tR[1][u], x = N+N;
for(qL+=N, qR+=N+1; qL<qR; qL/=2, qR/=2){
if(qL & 1) x = min(x, st[qL++]);
if(qR & 1) x = min(x, st[--qR]);
}
res[id] = x <= rx;
}
return res;
}
