#include <bits/stdc++.h>
using namespace std;
namespace{
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) FOR(i, 0, r)
#define FORD(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define F0RD(i, r) FORD(i, 0, r)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
#define dbg(x) "[" #x " = " << (x) << "]"
tcT> bool minimize(T& a, const T& b){ return a > b ? a = b, 1 : 0; }
tcT> bool maximize(T& a, const T& b){ return a < b ? a = b, 1 : 0; }
tcT> using vc = vector<T>;
tcT> using vvc = vc<vc<T>>;
using ll = long long;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vc<int>;
using vl = vc<ll>;
using vpi = vc<pi>;
using vpl = vc<pl>;
using vvi = vvc<int>;
using vvl = vvc<ll>;
using vvpi = vvc<pi>;
using vvpl = vvc<pl>;
const int MAX = 2e5 + 5;
struct SparseTableMin{
vvi st;
SparseTableMin(vi dat) : st(){
st.pb(dat);
int n = sz(dat);
for(int i = 1; (1 << i) <= n; ++i){
st.pb(vi(n - (1 << i) + 1));
F0R(j, n - (1 << i) + 1){
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}
int query(int l, int r){
int k = 31 - __builtin_clz(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
};
struct SparseTableMax{
vvi st;
SparseTableMax(vi dat) : st(){
st.pb(dat);
int n = sz(dat);
for(int i = 1; (1 << i) <= n; ++i){
st.pb(vi(n - (1 << i) + 1));
F0R(j, n - (1 << i) + 1){
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}
int query(int l, int r){
int k = 31 - __builtin_clz(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
};
struct DSU{
vi f;
DSU() : f() {}
DSU(int n) : f(n, -1) {}
int root(int u){
return f[u] < 0 ? u : (f[u] = root(f[u]));
}
bool join(int u, int v){
u = root(u); v = root(v);
if(u == v) return false;
if(f[u] > f[v]) swap(u, v);
f[u] += f[v];
f[v] = u;
return true;
}
bool isConnected(int a, int b){ return root(a) == root(b); }
} dsu;
namespace Tree{
struct Edge{
int v, wMin, wMax;
};
int dep[MAX], par[MAX], up[20][MAX], upMin[20][MAX], upMax[20][MAX];
vector<Edge> adj[MAX];
void dfsTree(int u){
for(auto [v, wMin, wMax] : adj[u]){
dep[v] = dep[u] + 1;
up[0][v] = u;
upMin[0][v] = wMin;
upMax[0][v] = wMax;
for(int i = 1; (1 << i) <= dep[v]; ++i){
up[i][v] = up[i - 1][up[i - 1][v]];
upMin[i][v] = min(upMin[i - 1][v], upMin[i - 1][up[i - 1][v]]);
upMax[i][v] = max(upMax[i - 1][v], upMax[i - 1][up[i - 1][v]]);
}
dfsTree(v);
}
}
void init(vector<tuple<int, int, int>> parent){
int nodes = sz(parent);
F0R(i, nodes){
auto [p, wMin, wMax] = parent[i];
par[i] = p;
if(p != -1){
adj[p].pb(Edge{i, wMin, wMax});
}
}
F0R(i, nodes){
if(par[i] == -1){
dfsTree(i);
}
}
}
pi getPath(int u, int v){
int wMin = 1e9, wMax = -1e9;
if(dep[u] < dep[v]) swap(u, v);
int k = dep[u] - dep[v];
while(k > 0){
int bit = 31 - __builtin_clz(k);
k -= (1 << bit);
minimize(wMin, upMin[bit][u]);
maximize(wMax, upMax[bit][u]);
u = up[bit][u];
}
if(u == v) return mp(wMin, wMax);
for(int i = 31 - __builtin_clz(dep[u]); i >= 0; --i){
if(dep[u] >= (1 << i) && up[i][u] != up[i][v]){
minimize(wMin, upMin[i][u]);
minimize(wMin, upMin[i][v]);
maximize(wMax, upMax[i][u]);
maximize(wMax, upMax[i][v]);
u = up[i][u]; v = up[i][v];
}
}
minimize(wMin, upMin[0][u]);
minimize(wMin, upMin[0][v]);
maximize(wMax, upMax[0][u]);
maximize(wMax, upMax[0][v]);
return mp(wMin, wMax);
}
}
namespace SegTree{
#define ls (id << 1)
#define rs (id << 1 | 1)
int st[MAX << 2];
void build(int id, int l, int r, vi& A){
if(l < r){
int mid = l + r >> 1;
build(ls, l, mid, A);
build(rs, mid + 1, r, A);
st[id] = min(st[ls], st[rs]);
} else{
st[id] = A[l];
}
}
int findLeft(int id, int l, int r, int u, int v, int bound){
if(v < l || u > r || st[id] >= bound) return -1;
if(l == r) return l;
int mid = l + r >> 1;
int res = findLeft(ls, l, mid, u, v, bound);
if(res == -1) res = findLeft(rs, mid + 1, r, u, v, bound);
return res;
}
int findRight(int id, int l, int r, int u, int v, int bound){
if(v < l || u > r || st[id] >= bound) return -1;
if(l == r) return l;
int mid = l + r >> 1;
int res = findRight(rs, mid + 1, r, u, v, bound);
if(res == -1) res = findRight(ls, l, mid, u, v, bound);
return res;
}
}
int N, M, nxt[MAX], id[MAX];
void myInitialize(vector<int> A, vector<int> B){
N = sz(A); M = sz(B);
stack<int> st;
F0RD(i, N){
while(!st.empty() && A[st.top()] <= A[i]) st.pop();
nxt[i] = (st.empty() ? N : st.top());
st.push(i);
}
SegTree::build(1, 0, M - 1, B);
vvi nxtLift(20, vi(N + 1, N));
F0R(i, N) nxtLift[0][i] = nxt[i];
FOR(i, 1, 20){
F0R(j, N){
nxtLift[i][j] = nxtLift[i - 1][nxtLift[i - 1][j]];
}
}
vi par;
vpi ed;
int nodes = 0;
map<tuple<int, int, int>, int> ids; //[row, l, r]
vi row0(M);
F0R(i, M){
row0[i] = A[0] > B[i];
}
SparseTableMax maxB(B);
auto extendLeft = [&](int i, int L){
int l = 0, r = L - 1, newL = L;
while(l <= r){
int mid = l + r >> 1;
if(A[i] > maxB.query(mid, L)) newL = mid, r = mid - 1;
else l = mid + 1;
}
return newL;
};
auto extendRight = [&](int i, int R){
int l = R + 1, r = M - 1, newR = R;
while(l <= r){
int mid = l + r >> 1;
if(A[i] > maxB.query(R, mid)) newR = mid, l = mid + 1;
else r = mid - 1;
}
return newR;
};
SparseTableMin minA(A), minB(B);
auto reachable = [&](int lRow, int rRow, int x, int y){ //from lr -> rr using some columns in x and y
int u = minA.query(lRow, rRow);
int l = SegTree::findLeft(1, 0, M - 1, x, y, u);
if(l == -1) return mp(-1, -1);
int r = SegTree::findRight(1, 0, M - 1, x, y, u);
return mp(l, r);
};
auto findFirstGreater = [&](int i, int target){
for(int step = 17; step >= 0; --step){
if(nxtLift[step][i] < N && A[nxtLift[step][i]] <= target) i = nxtLift[step][i];
}
return nxtLift[0][i];
};
function<int(int, int, int)> recurse = [&](int i, int l, int r){
if(ids.count(mt(i, l, r))) return ids[mt(i, l, r)];
ids[mt(i, l, r)] = nodes++;
par.pb(-1);
ed.eb(-1, -1);
int u = nodes - 1;
if(nxt[i] == N) return u;
if(l == 0 && r == M - 1) return u;
int target = min((l > 0 ? B[l - 1] : (int)1e9 + 1), (r < M - 1 ? B[r + 1] : (int)1e9 + 1));
int upi = findFirstGreater(i, target);
if(upi == N) return u;
pi cand = reachable(i, upi, l, r);
if(cand != mp(-1, -1)){
int upl = extendLeft(upi, l), upr = extendRight(upi, r);
par[u] = recurse(upi, upl, upr);
ed[u] = cand;
}
return u;
};
F0R(i, M) if(row0[i] == 1){
int j = i;
while(i + 1 < M && row0[i + 1]) ++i;
int u = recurse(0, j, i);
FOR(k, j, i + 1) id[k] = u;
}
dsu = DSU(nodes);
vector<tuple<int, int, int>> info(nodes, mt(-1, -1, -1));
F0R(i, nodes) if(par[i] != -1){
dsu.join(par[i], i);
info[i] = mt(par[i], ed[i].ss, ed[i].ff);
}
Tree::init(info);
}
int myQuery(int L, int R, int S, int T){
S = id[S];
T = id[T];
if(S == T) return true;
if(!dsu.isConnected(S, T)) return false;
auto [minW, maxW] = Tree::getPath(S, T);
return L <= minW && minW <= maxW && maxW <= R;
}
}
void initialize(vector<int> A, vector<int> B){
myInitialize(A, B);
}
int can_reach(int L, int R, int S, int T){
return myQuery(L, R, S, T);
}
