#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
DSU(int n): p(n), sz(n,1) { iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
void unite(int a,int b){
a=find(a); b=find(b);
if(a==b) return;
if(sz[a]<sz[b]) swap(a,b);
p[b]=a; sz[a]+=sz[b];
}
};
int N,M;
vector<int> T,H;
vector<int> linkRight; // linkRight[c] = furthest column reachable from col c in row 0
vector<int> maxReach; // prefix max of linkRight
inline int id(int i,int j){ return i*M + j; }
void initialize(vector<int> t, vector<int> h) {
T = t; H = h;
N = T.size(); M = H.size();
// Step 1: mark free cells
vector<char> freecell((long long)N * M, 0);
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(T[i] > H[j]) freecell[id(i,j)] = 1;
}
}
// Step 2: build DSU for all free cells
DSU dsu(N*M);
// vertical edges
for(int i=0;i<N-1;i++){
for(int j=0;j<M;j++){
if(freecell[id(i,j)] && freecell[id(i+1,j)])
dsu.unite(id(i,j), id(i+1,j));
}
}
// horizontal edges
for(int i=0;i<N;i++){
for(int j=0;j<M-1;j++){
if(freecell[id(i,j)] && freecell[id(i,j+1)])
dsu.unite(id(i,j), id(i,j+1));
}
}
// Step 3: For each component touching row 0, find min & max column in row 0
vector<int> minCol(N*M, M), maxCol(N*M, -1);
for(int j=0;j<M;j++){
if(freecell[id(0,j)]){
int root = dsu.find(id(0,j));
minCol[root] = min(minCol[root], j);
maxCol[root] = max(maxCol[root], j);
}
}
// Step 4: Build linkRight for each col in row 0
linkRight.assign(M, -1);
for(int j=0;j<M;j++){
if(freecell[id(0,j)]){
int root = dsu.find(id(0,j));
linkRight[j] = maxCol[root];
} else {
linkRight[j] = j; // blocked cell: can only "reach" itself
}
}
// Step 5: Build prefix maxReach
maxReach.assign(M, -1);
int curMax = -1;
for(int j=0;j<M;j++){
curMax = max(curMax, linkRight[j]);
maxReach[j] = curMax;
}
}
bool can_reach(int L, int R, int S, int D) {
if(S > D) swap(S,D);
// Check both start & end are free
if(maxReach[S] < S || maxReach[D] < D) return false; // blocked cells
// Check if reachable without leaving [L,R]
if(S < L || D > R) return false;
// The precomputed maxReach must cover D within [L,R]
return maxReach[S] >= D;
}
