#include <bits/stdc++.h>
using namespace std;
namespace Obstacles {
// ---------- Segment tree trên H: min + tìm rào H>=t ----------
struct SegTree {
int n;
vector<int> mn, mx; // mn: min(H), mx: max(H) để prune các truy vấn GE
void build(int id, int l, int r, const vector<int>& a) {
if (l == r) { mn[id] = mx[id] = a[l]; return; }
int m = (l + r) >> 1;
build(id<<1, l, m, a);
build(id<<1|1, m+1, r, a);
mn[id] = min(mn[id<<1], mn[id<<1|1]);
mx[id] = max(mx[id<<1], mx[id<<1|1]);
}
void init(const vector<int>& a) {
n = (int)a.size();
mn.assign(4*n, INT_MAX);
mx.assign(4*n, INT_MIN);
if (n) build(1, 0, n-1, a);
}
int qmin(int id, int l, int r, int ql, int qr) const {
if (ql > qr || qr < l || r < ql) return INT_MAX;
if (ql <= l && r <= qr) return mn[id];
int m = (l + r) >> 1;
return min(qmin(id<<1, l, m, ql, qr), qmin(id<<1|1, m+1, r, ql, qr));
}
int qmin(int l, int r) const {
if (l > r) return INT_MAX; // guard đoạn rỗng
return qmin(1, 0, n-1, l, r);
}
// first index in [ql,qr] with H[idx] >= t, or -1
int first_ge(int id, int l, int r, int ql, int qr, int t) const {
if (ql > qr || qr < l || r < ql || mx[id] < t) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int left = first_ge(id<<1, l, m, ql, qr, t);
return (left != -1) ? left : first_ge(id<<1|1, m+1, r, ql, qr, t);
}
int first_ge(int l, int r, int t) const {
if (l > r) return -1;
return first_ge(1, 0, n-1, l, r, t);
}
// last index in [ql,qr] with H[idx] >= t, or -1
int last_ge(int id, int l, int r, int ql, int qr, int t) const {
if (ql > qr || qr < l || r < ql || mx[id] < t) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int right = last_ge(id<<1|1, m+1, r, ql, qr, t);
return (right != -1) ? right : last_ge(id<<1, l, m, ql, qr, t);
}
int last_ge(int l, int r, int t) const {
if (l > r) return -1;
return last_ge(1, 0, n-1, l, r, t);
}
};
int N, M;
vector<int> Trow, Hcol;
vector<int> prefMinT, prefMaxT;
SegTree segH;
// sâu nhất r sao cho prefixMin(0..r) > h ; -1 nếu không có
inline int last_r_with_prefMin_gt(int h) {
int lo = 0, hi = N - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (prefMinT[mid] > h) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return ans;
}
// dải cột quanh X trong [L,R] với điều kiện H < t
inline pair<int,int> span_around(int L, int R, int X, int t) {
// rào trái/phải giới hạn trong [L..X] và [X..R]
int left_bar = segH.last_ge(L, X, t);
int right_bar = segH.first_ge(X, R, t);
int Lb = max(L, left_bar + 1);
int Rb = min(R, (right_bar == -1 ? R : right_bar - 1));
return {Lb, Rb};
}
} // namespace Obstacles
using namespace Obstacles;
// -------- required API --------
void initialize(vector<int> T, vector<int> H) {
Trow = move(T); Hcol = move(H);
N = (int)Trow.size(); M = (int)Hcol.size();
// prefix min/max của T
prefMinT.assign(N, 0);
prefMaxT.assign(N, 0);
for (int i = 0; i < N; ++i) {
if (i == 0) prefMinT[i] = prefMaxT[i] = Trow[i];
else {
prefMinT[i] = min(prefMinT[i-1], Trow[i]);
prefMaxT[i] = max(prefMaxT[i-1], Trow[i]);
}
}
// segment tree trên H
segH.init(Hcol);
}
bool can_reach(int L, int R, int S, int D) {
// Guard theo mô tả đề: (0,S) và (0,D) đều hợp lệ, nhưng ta vẫn chặn an toàn.
if (!(Trow[0] > Hcol[S] && Trow[0] > Hcol[D])) return false;
// Dải hàng-0 quanh D (H < T[0])
int t0 = Trow[0];
auto dseg = span_around(L, R, D, t0);
int DL = dseg.first, DR = dseg.second; // luôn DL ≤ D ≤ DR
// Khởi tạo dải quanh S với tcur = T[0]
int tcur = t0;
auto sseg = span_around(L, R, S, tcur);
int Lb = sseg.first, Rb = sseg.second; // luôn Lb ≤ S ≤ Rb
// Lặp mở rộng theo "thang máy" tốt nhất; số vòng ≤ 11 (miền giá trị 0..10)
for (int iter = 0; iter < 20; ++iter) { // 20 = guard thừa an toàn
// Độ ẩm nhỏ nhất trong dải hiện tại
int hmin = segH.qmin(Lb, Rb); // ∈ [0..10]
int rmax = last_r_with_prefMin_gt(hmin);
if (rmax < 0) return false; // không thể đi xuống (guard)
// Ngưỡng ngang tốt nhất sau khi đi xuống ≤ rmax
int tnew = prefMaxT[rmax];
// Dải mới quanh S theo tnew
auto sseg2 = span_around(L, R, S, tnew);
int L2 = sseg2.first, R2 = sseg2.second;
// Kiểm tra khả năng kết thúc tại (0,D):
// cần giao giữa dải mới của S và dải hàng-0 của D,
// và có cột trên giao đủ "khô" để leo thẳng về hàng 0.
int IL = max(L2, DL), IR = min(R2, DR);
if (IL <= IR) {
int h_inter = segH.qmin(IL, IR); // INT_MAX nếu rỗng (nhưng đã IL<=IR)
if (h_inter < prefMinT[rmax]) return true;
}
// Không thể nới thêm → bế tắc
if (tnew <= tcur) return false;
// Cập nhật cho vòng tiếp
tcur = tnew;
Lb = L2; Rb = R2;
}
return false; // không tới được (guard)
}
