#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -4e18; // sentinel for impossible B
/*---------------------------------------------------------------*/
/* segment tree for (max B , index) */
struct SegMaxB {
int n;
vector<pair<ll,int>> t; // (B , index)
SegMaxB(int _n=0){init(_n);}
void init(int _n){
n=1; while(n<_n) n<<=1;
t.assign(2*n, {NEG,-1});
}
// set position p (0‑based)
void setVal(int p, ll B, int idx){
p+=n;
t[p] = {B, idx};
for(p>>=1; p; p>>=1){
t[p] = (t[p<<1].first >= t[p<<1|1].first) ? t[p<<1] : t[p<<1|1];
}
}
// query max on [l,r] inclusive
pair<ll,int> query(int l,int r){
if(l>r) return {NEG,-1};
l+=n; r+=n;
pair<ll,int> ans = {NEG,-1};
while(l<=r){
if(l&1){
if(t[l].first > ans.first) ans = t[l];
++l;
}
if(!(r&1)){
if(t[r].first > ans.first) ans = t[r];
--r;
}
l>>=1; r>>=1;
}
return ans;
}
};
/*---------------------------------------------------------------*/
/* segment tree for range maximum of H */
struct SegMaxH {
int n;
vector<int> t;
SegMaxH(int _n=0){init(_n);}
void init(int _n){
n=1; while(n<_n) n<<=1;
t.assign(2*n, INT_MIN);
}
void setVal(int p, int val){
p+=n;
t[p]=val;
for(p>>=1; p; p>>=1) t[p]=max(t[p<<1], t[p<<1|1]);
}
int query(int l,int r){ // inclusive
if(l>r) return INT_MIN;
l+=n; r+=n;
int ans = INT_MIN;
while(l<=r){
if(l&1) ans = max(ans, t[l++]);
if(!(r&1)) ans = max(ans, t[r--]);
l>>=1; r>>=1;
}
return ans;
}
};
/*---------------------------------------------------------------*/
/* sparse table for range minimum/maximum (integer) */
struct SparseTable {
int N, K;
vector<vector<int>> st;
vector<int> lg;
bool isMin; // true -> min, false -> max
SparseTable(){}
SparseTable(const vector<int> &a, bool _isMin){
build(a,_isMin);
}
void build(const vector<int> &a, bool _isMin){
isMin = _isMin;
N = (int)a.size();
K = 1;
while((1<<K) <= N) ++K;
lg.assign(N+1,0);
for(int i=2;i<=N;i++) lg[i]=lg[i/2]+1;
st.assign(K, vector<int>(N));
st[0]=a;
for(int k=1;k<K;k++){
for(int i=0;i+(1<<k)<=N;i++){
if(isMin)
st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
else
st[k][i]=max(st[k-1][i], st[k-1][i+(1<<(k-1))]);
}
}
}
// query on [l,r] inclusive
int query(int l,int r) const{
if(l>r) return isMin?INT_MAX:INT_MIN;
int k = lg[r-l+1];
if(isMin)
return min(st[k][l], st[k][r-(1<<k)+1]);
else
return max(st[k][l], st[k][r-(1<<k)+1]);
}
};
/*---------------------------------------------------------------*/
/* global data */
static vector<int> T, H;
static vector<int> prefMin, prefMax;
static vector<int> deepest; // -1 … N-1
static vector<ll> B; // -inf for useless columns
static vector<int> blockId; // -1 for non‑free0
static vector<int> blockLeft, blockRight; // per block
static SegMaxB segB;
static SegMaxH segH;
static SparseTable stLeftGood, stRightGood; // leftGood min , rightGood max
static vector<int> leftGood, rightGood; // size M-1
/*---------------------------------------------------------------*/
void initialize(vector<int> TT, vector<int> HH){
T.swap(TT); H.swap(HH);
int N = T.size();
int M = H.size();
/* prefix minima / maxima of T */
prefMin.resize(N);
prefMax.resize(N);
for(int i=0;i<N;i++){
prefMin[i] = (i==0? T[i] : min(prefMin[i-1], T[i]));
prefMax[i] = (i==0? T[i] : max(prefMax[i-1], T[i]));
}
/* deepest and B for every column */
deepest.assign(M, -1);
B.assign(M, NEG);
for(int j=0;j<M;j++){
// first index where prefMin <= H[j]
int lo=0, hi=N-1, pos=N;
while(lo<=hi){
int mid=(lo+hi)/2;
if(prefMin[mid] <= H[j]){
pos=mid;
hi=mid-1;
}else lo=mid+1;
}
if(pos==0) deepest[j] = -1;
else if(pos==N) deepest[j] = N-1;
else deepest[j] = pos-1;
if(deepest[j] >= 0) B[j] = prefMax[deepest[j]];
}
/* free0 columns and block decomposition */
blockId.assign(M, -1);
vector<int> blockOfCol; // only for free columns
blockLeft.clear(); blockRight.clear();
int curBlk = -1;
for(int j=0;j<M;j++){
if(H[j] < T[0]){
if(curBlk==-1){
curBlk = (int)blockLeft.size();
blockLeft.push_back(j);
blockRight.push_back(j);
blockOfCol.push_back(curBlk);
}else{
blockRight[curBlk]=j;
blockOfCol.push_back(curBlk);
}
blockId[j]=curBlk;
}else{
curBlk=-1;
blockOfCol.push_back(-1);
}
}
/* segment tree for max B (only for free0 columns) */
segB.init(M);
for(int j=0;j<M;j++){
if(B[j]!=NEG) segB.setVal(j, B[j], j);
}
/* segment tree for max H */
segH.init(M);
for(int j=0;j<M;j++) segH.setVal(j, H[j]);
/* ----- compute leftGood and rightGood ---------------------- */
// first next index with H >= B
vector<int> nextGe(M, M);
for(int j=0;j<M;j++){
if(B[j]==NEG){ nextGe[j]=j+1; continue; }
int lo=j+1, hi=M-1, pos=M;
while(lo<=hi){
int mid=(lo+hi)/2;
if(H[mid] >= B[j]){
pos=mid; hi=mid-1;
}else lo=mid+1;
}
nextGe[j]=pos;
}
// rightLimit from (3)
vector<int> rightLimit(M, -2); // -2 means cannot cross any border
for(int j=0;j<M;j++){
if(B[j]==NEG) continue;
rightLimit[j] = nextGe[j]-2; // may become -1, -2 etc.
}
// sweep left to right, maintain active columns (rightLimit >= cur)
leftGood.assign(max(0,M-1), -1);
vector<vector<int>> deactivate(M); // at border x we deactivate cols with rightLimit == x-1
for(int j=0;j<M;j++){
if(rightLimit[j]>=j){
int stop = rightLimit[j]+1; // first border where it stops
if(stop < M) deactivate[stop].push_back(j);
}
}
// segment tree for max index among active columns
struct SegIdx {
int n; vector<int> t;
SegIdx(int _n=0){init(_n);}
void init(int _n){
n=1; while(n<_n) n<<=1;
t.assign(2*n, -1);
}
void setVal(int p, int v){
p+=n; t[p]=v;
for(p>>=1;p;p>>=1) t[p]=max(t[p<<1], t[p<<1|1]);
}
int query(int l,int r){
if(l>r) return -1;
l+=n; r+=n;
int ans=-1;
while(l<=r){
if(l&1) ans=max(ans,t[l++]);
if(!(r&1)) ans=max(ans,t[r--]);
l>>=1; r>>=1;
}
return ans;
}
} segIdx;
segIdx.init(M);
// initially none active
for(int border=0; border<M-1; ++border){
// activate column border (it becomes usable exactly at its own border)
if(rightLimit[border]>=border){
segIdx.setVal(border, border);
}
// deactivate columns that stop before next border
for(int col: deactivate[border+1]){
segIdx.setVal(col, -1);
}
leftGood[border] = segIdx.query(0, border);
}
// now rightGood (mirror)
vector<int> prevGe(M, -1);
for(int j=0;j<M;j++){
if(B[j]==NEG){ prevGe[j]=j-1; continue; }
int lo=0, hi=j-1, pos=-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(H[mid] >= B[j]){
pos=mid; lo=mid+1;
}else hi=mid-1;
}
prevGe[j]=pos;
}
vector<int> leftLimit(M, -2);
for(int j=0;j<M;j++){
if(B[j]==NEG) continue;
leftLimit[j] = prevGe[j]+1; // first border that can be crossed from right side
}
// sweep right to left, maintain active columns (leftLimit <= cur)
rightGood.assign(max(0,M-1), M);
vector<vector<int>> activate(M); // at border x we activate columns with leftLimit == x
for(int j=0;j<M;j++){
if(leftLimit[j]<=j-1){
int start = leftLimit[j];
if(start>=0) activate[start].push_back(j);
}
}
// segment tree for minimal index among active columns
struct SegMinIdx {
int n; vector<int> t;
SegMinIdx(int _n=0){init(_n);}
void init(int _n){
n=1; while(n<_n) n<<=1;
t.assign(2*n, INT_MAX);
}
void setVal(int p, int v){
p+=n; t[p]=v;
for(p>>=1;p;p>>=1) t[p]=min(t[p<<1], t[p<<1|1]);
}
int query(int l,int r){
if(l>r) return INT_MAX;
l+=n; r+=n;
int ans=INT_MAX;
while(l<=r){
if(l&1) ans=min(ans,t[l++]);
if(!(r&1)) ans=min(ans,t[r--]);
l>>=1; r>>=1;
}
return ans;
}
} segMinIdx;
segMinIdx.init(M);
// initially none active
for(int border=M-2; border>=0; --border){
// activate columns that become usable at this border
for(int col: activate[border]){
segMinIdx.setVal(col, col);
}
// columns that are to the left of this border are not usable any more,
// but we never deactivate because once leftLimit <= border it stays true.
int cur = segMinIdx.query(border+1, M-1);
if(cur==INT_MAX) cur = M; // meaning not existing
rightGood[border] = cur;
}
// build sparse tables for leftGood (min) and rightGood (max)
if(M>=2){
stLeftGood = SparseTable(leftGood, true); // min
stRightGood = SparseTable(rightGood, false); // max
}
}
/*---------------------------------------------------------------*/
bool can_reach(int L, int R, int S, int D){
if(S==D) return true;
int blkS = blockId[S];
int blkD = blockId[D];
if(blkS==-1 || blkD==-1) return false; // should not happen
if(blkS == blkD) return true; // same row‑0 block
// intersection of destination block with the interval
int dL = max(L, blockLeft[blkD]);
int dR = min(R, blockRight[blkD]);
if(dL > dR) return false; // destination block not inside interval
// intersection of start block with the interval
int sL = max(L, blockLeft[blkS]);
int sR = min(R, blockRight[blkS]);
if(sL > sR) return false;
// best (max B) column inside start block part
auto bestStart = segB.query(sL, sR);
ll BmaxStart = bestStart.first;
int p = bestStart.second; // column index of that best start column
// best (max B) column inside destination block part
auto bestDest = segB.query(dL, dR);
ll BmaxDest = bestDest.first;
// threshold V
ll V = min(BmaxStart, BmaxDest);
if(V==NEG) return false; // should not happen
// column q of destination block that is closest to p
int q;
if(S < D) q = dL; // leftmost column of dest block
else q = dR; // rightmost column of dest block
int lo = min(p,q), hi = max(p,q);
int maxH = segH.query(lo, hi);
return ( (ll)maxH < V );
}
