#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif
// 0-indexed
template<class T>
struct sparse_table{
vector<vector<T>> arr;
vector<int> floorlog;
function<T(T, T)> func;
int n;
sparse_table(){}
sparse_table(vector<T> & vec, function<T(T, T)> f) : n(sz(vec)), floorlog(sz(vec) + 1), func(f){
for(int i = 0; (1 << i) <= n; i++){
for(int j = (1 << i); j < (1 << (i + 1)) && j <= n; j++)
floorlog[j] = i;
}
arr.assign(floorlog[n] + 1, vector<T>(n));
for(int i = n - 1; i >= 0; i--){
arr[0][i] = vec[i];
for(int j = 1; i + (1 << j) <= n; j++){
arr[j][i] = func(arr[j - 1][i], arr[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int i, int j){
int k = floorlog[j - i + 1];
return func(arr[k][i], arr[k][j - (1 << k) + 1]);
}
pair<int, int> getRange(int i, function<bool(T)> pred) {
int lo = i, hi = n - 1;
while(lo < hi){
int mid = (lo + hi + 1) / 2;
if(pred(get(i, mid))) lo = mid;
else hi = mid - 1;
}
int rgt = lo;
lo = 0, hi = i;
while(lo < hi){
int mid = (lo + hi) / 2;
if(pred(get(mid, i))) hi = mid;
else lo = mid + 1;
}
int lft = lo;
return {lft, rgt};
}
};
struct Tree{
vector<vector<int>> adj;
vector<int> A, B, C;
vector<ll> D; // weighted edges
vector<int> pos, tour, depth, pos_end; // for O(1) lca after O(n logn) precomputation
vector<vector<int>> table;
int n, m;
Tree(){}
Tree(int n) : n(n), A(n - 1), B(n - 1), C(n - 1), adj(n), m(0){};
void add_edge(int u, int v, int w = 1){
if(u >= n || v >= n) {
n = max(n, max(u, v) + 1);
A.resize(n - 1); B.resize(n - 1); C.resize(n - 1);
adj.resize(n);
}
adj[u].push_back(m);
adj[v].push_back(m);
A[m] = u; B[m] = v; C[m++] = w;
}
int argmin(int i, int j) { return depth[i] < depth[j] ? i : j; }
void rootify(int r) {
pos.resize(n);
pos_end.resize(n);
D.resize(n);
function<void (int,int,int)> dfs = [&](int u, int p, int d) {
pos[u] = pos_end[u] = depth.size();
tour.push_back(u);
depth.push_back(d);
for (int ind: adj[u]) {
int v = A[ind] ^ B[ind] ^ u;
if (v != p) {
D[v] = D[u] + C[ind];
dfs(v, u, d+1);
pos_end[u] = depth.size();
tour.push_back(u);
depth.push_back(d);
}
}
}; dfs(r, r, 0);
int logn = __lg(tour.size());
table.resize(logn+1, vector<int>(tour.size()));
iota(all(table[0]), 0);
for (int h = 0; h < logn; ++h)
for (int i = 0; i+(1<<h) < tour.size(); ++i)
table[h+1][i] = argmin(table[h][i], table[h][i+(1<<h)]);
}
int lca(int u, int v) {
int i = pos[u], j = pos[v]; if (i > j) swap(i, j);
int h = __lg(j - i + 1);
return i == j ? u : tour[argmin(table[h][i], table[h][j-(1<<h)+1])];
}
inline int getDepth(int u){
return depth[pos[u]];
}
int dist(int u, int v){
int l = lca(u, v);
return D[u] + D[v] - 2 * D[l];
}
};
struct TimedDSU{
int n;
vector<int> par, label;
Tree T;
TimedDSU() : n(0), T() {}
TimedDSU(int n, int def_label): n(n), par(n), label(n, def_label), T(n){
iota(par.begin(), par.end(), 0);
}
int root(int x){
return x == par[x] ? x : (par[x] = root(par[x]));
}
void merge(int u, int v, int l){
u = root(u); v = root(v);
if(u == v) return;
int w = n++;
par[u] = par[v] = w;
par.push_back(w);
label.push_back(l);
T.add_edge(u, w);
T.add_edge(v, w);
}
void postprocess(){
int w = n++;
label.push_back(-1);
for(int i = 0; i < w; i++) if(par[i] == i) T.add_edge(i, w);
T.rootify(w);
}
int lcaLabel(int u, int v){
return label[T.lca(u, v)];
}
};
int n, m;
TimedDSU dsu_L, dsu_R;
void initialize(std::vector<int> T, std::vector<int> H) {
n = T.size(), m = H.size();
vector<int> prefMax(n);
vector<int> lft(m), rgt(m), pos(m);
vector<vector<int>> at_lft(m), at_rgt(m);
sparse_table<int> st_H(H, [](int a, int b){return max(a, b);});
sparse_table<int> st_T(T, [](int a, int b){return min(a, b);});
for(int i = 0; i < n; i++){
prefMax[i] = i == 0 ? 0: (T[i] > T[prefMax[i-1]] ? i : prefMax[i-1]);
}
for(int i = 0; i < m; i++){
if(T[0] > H[i])
pos[i] = prefMax[st_T.getRange(0, [&](int x){return x > H[i];}).second];
else pos[i] = -1;
}
dsu_L = TimedDSU(m, m - 1);
dsu_R = TimedDSU(m, 0);
stack<int> stk;
for(int i = 0; i < m; i++){
while(!stk.empty() && H[stk.top()] >= H[i])
stk.pop();
lft[i] = stk.empty() ? -1: stk.top();
if(lft[i] != -1) {
at_lft[lft[i]].push_back(i);
}
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i = m - 1; i >= 0; i--){
while(!stk.empty() && H[stk.top()] > H[i]) stk.pop();
rgt[i] = stk.empty() ? m: stk.top();
if(rgt[i] != m) {
at_rgt[rgt[i]].push_back(i);
}
stk.push(i);
}
for(int L = m - 1; L >= 0; L--){
for(int i: at_lft[L]){
int j = pos[i];
if(j == -1) continue;
pair<int, int> rng = st_H.getRange(i, [&](int x){return x < T[j];});
if(rgt[i] > rng.second){
dsu_L.merge(i, L, L);
}
}
if(pos[L] != -1){
pair<int, int> rng = st_H.getRange(L, [&](int x){return x < T[pos[L]];});
if(rgt[L] <= rng.second){
dsu_L.merge(L, pos[L], L);
}
}
}
for(int R = 0; R < m; R++){
for(int i: at_rgt[R]){
int j = pos[i];
if(j == -1) continue;
pair<int, int> rng = st_H.getRange(i, [&](int x){return x < T[j];});
if(lft[i] < rng.first){
dsu_R.merge(i, R, R);
}
}
if(lft[R] >= 0) dsu_R.merge(lft[R], R, R);
if(pos[R] != -1){
pair<int, int> rng = st_H.getRange(R, [&](int x){return x < T[pos[R]];});
if(lft[R] >= rng.first){
dsu_R.merge(R, pos[R], R);
}
}
}
dsu_L.postprocess();
dsu_R.postprocess();
return;
}
bool can_reach(int L, int R, int S, int D) {
int l = dsu_L.lcaLabel(S, D);
int r = dsu_R.lcaLabel(S, D);
if(l == -1 || r == -1) return false;
return L <= l && R >= r;
}
