#include <bits/stdc++.h>
using namespace std;
namespace Obstacles {
// ----- Hằng số -----
static const int MAXV = 11; // vì T,H ∈ [0..10]
// ----- Dữ liệu -----
int N, M;
vector<int> Trow, Hcol;
// prefix min/max của T
vector<int> prefMinT, prefMaxT;
// lastGreater[h] = chỉ số r lớn nhất sao cho prefMinT[r] > h (h = 0..10)
int lastGreater[MAXV];
// Sparse Table cho RMQ min(H)
vector<int> lg2;
vector<vector<int>> st; // st[k][i] = min trên [i, i+2^k-1]
// Với mỗi ngưỡng t (0..10): rào trước/sau gần nhất có H >= t
vector<vector<int>> prevGE, nextGE; // size [11][M]
// ----- RMQ min trên H -----
inline int rmqMinH(int l, int r) {
if (l > r) return INT_MAX;
int len = r - l + 1, k = lg2[len];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
// ----- Dải cột quanh S trong [L,R] với điều kiện H < t -----
inline pair<int,int> component_bounds(int L, int R, int S, int t) {
// rào trái = chỉ số cuối cùng ở [L..S] có H >= t ; rào phải = chỉ số đầu tiên ở [S..R] có H >= t
int Lbar = prevGE[t][S];
int Rbar = nextGE[t][S];
int Lb = max(L, Lbar + 1);
int Rb = min(R, (Rbar == M ? R : Rbar - 1));
return {Lb, Rb};
}
} // namespace Obstacles
using namespace Obstacles;
// ----------------- initialize -----------------
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.resize(N);
prefMaxT.resize(N);
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]);
}
}
// lastGreater[h] = r lớn nhất có prefMinT[r] > h (chạy O(N*11) an toàn)
for (int h = 0; h < MAXV; ++h) lastGreater[h] = -1;
for (int r = 0; r < N; ++r) {
int upTo = min(prefMinT[r]-1, MAXV-1);
for (int h = 0; h <= upTo; ++h) lastGreater[h] = r;
}
// Sparse Table trên H
lg2.assign(M + 1, 0);
for (int i = 2; i <= M; ++i) lg2[i] = lg2[i >> 1] + 1;
int K = lg2[M];
st.assign(K + 1, vector<int>(M));
for (int j = 0; j < M; ++j) st[0][j] = Hcol[j];
for (int k = 1; k <= K; ++k) {
int half = 1 << (k - 1);
for (int j = 0; j + (1 << k) <= M; ++j) {
st[k][j] = min(st[k-1][j], st[k-1][j + half]);
}
}
// prevGE/nextGE cho mọi ngưỡng t = 0..10
prevGE.assign(MAXV, vector<int>(M));
nextGE.assign(MAXV, vector<int>(M));
for (int t = 0; t < MAXV; ++t) {
int last = -1;
for (int j = 0; j < M; ++j) {
prevGE[t][j] = last;
if (Hcol[j] >= t) last = j;
}
int nxt = M;
for (int j = M - 1; j >= 0; --j) {
nextGE[t][j] = nxt;
if (Hcol[j] >= t) nxt = j;
}
}
}
// ----------------- can_reach -----------------
bool can_reach(int L, int R, int S, int D) {
// Bảo đảm đầu vào hợp lệ theo đề; kiểm tra an toàn:
if (!(Trow[0] > Hcol[S] && Trow[0] > Hcol[D])) return false;
// Dải hàng-0 của D (chỉ theo T[0]): nơi ta có thể "trồi lên" để kết thúc.
auto dseg = component_bounds(L, R, D, Trow[0]);
int DL = dseg.first, DR = dseg.second;
// Độ sâu tối đa có thể trồi lên ở dải của D: rCap = r(h_D)
int hD = rmqMinH(DL, DR);
int rCap = lastGreater[hD]; // >= 0 vì (0,D) đi được ⇒ hD < T[0]
// Khởi tạo dải quanh S với t = T[0]
int tcur = Trow[0];
auto sseg = component_bounds(L, R, S, tcur);
int Lb = sseg.first, Rb = sseg.second;
// Nếu hiện tại đã chạm dải của D ⇒ xong
if (max(Lb, DL) <= min(Rb, DR)) return true;
// Mở rộng ngưỡng nhưng KHÔNG xuống sâu hơn rCap
for (int iter = 0; iter < MAXV + 5; ++iter) { // 11 ngưỡng, +guard
if (Lb > Rb) return false; // phòng hờ, thực tế không xảy ra vì S∈[Lb,Rb]
int hmin = rmqMinH(Lb, Rb);
int rmax = lastGreater[hmin];
int rAllowed = (rCap < rmax ? rCap : rmax); // không vượt độ sâu cho phép ở dải D
if (rAllowed < 0) return false;
int tnew = prefMaxT[rAllowed];
if (tnew <= tcur) return false; // không thể nới thêm
tcur = tnew;
sseg = component_bounds(L, R, S, tcur);
Lb = sseg.first; Rb = sseg.second;
if (max(Lb, DL) <= min(Rb, DR)) return true; // dải của S đã chạm dải hàng-0 của D
}
return false; // guard
}
