// Your solution code here
#include <bits/stdc++.h>
using namespace std;
/*
IOI 2025 "Obstacles for a Llama" – specialized variant where L=0, R=M-1 always.
We preprocess the unique connected component (in the whole grid of free cells)
that each top-row column belongs to, then each query is O(1).
Key ingredients (adapted from known solution ideas for this task):
- nearest strictly smaller humidity on left/right (lf, rg)
- range maximum query on H to test whether a whole horizontal interval can be crossed
- bestTemp(h): maximum temperature reachable by going down using a column of humidity h
(i.e., among rows r such that min_{0..r} T > h)
*/
static int N_, M_;
static vector<int> T_, H_;
static vector<int> prefMinT_; // prefMinT_[i] = min(T[0..i]) (non-increasing)
static vector<int> prefMaxT_; // prefMaxT_[i] = max(T[0..i]) (non-decreasing)
static vector<int> lg2_;
static vector<vector<int>> stMaxH_; // sparse table for max on H
static vector<int> lf_, rg_; // nearest strictly smaller humidity indices
static vector<int> minVal_; // minVal_[j] = minimal humidity value reachable from column j (top row)
static vector<int> compL_, compR_; // final component interval [L,R] under threshold bestTemp(minVal)
static inline int rangeMaxH(int l, int r) {
if (l > r) std::swap(l, r);
int len = r - l + 1;
int k = lg2_[len];
return max(stMaxH_[k][l], stMaxH_[k][r - (1 << k) + 1]);
}
// bestTemp(h): max temperature T[x] among rows x where prefMinT_[x] > h.
// If no such row exists, return -1.
static inline int bestTemp(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 == -1 ? -1 : prefMaxT_[ans]);
}
static inline int leftBoundary(int pos, int t) {
// smallest L in [0..pos] such that max(H[L..pos]) < t
int lo = 0, hi = pos, ans = pos;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (rangeMaxH(mid, pos) < t) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return ans;
}
static inline int rightBoundary(int pos, int t) {
// largest R in [pos..M-1] such that max(H[pos..R]) < t
int lo = pos, hi = M_ - 1, ans = pos;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (rangeMaxH(pos, mid) < t) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
void initialize(std::vector<int> T, std::vector<int> H) {
T_ = std::move(T);
H_ = std::move(H);
N_ = (int)T_.size();
M_ = (int)H_.size();
// prefix min/max on T
prefMinT_.assign(N_, 0);
prefMaxT_.assign(N_, 0);
{
int mn = INT_MAX, mx = INT_MIN;
for (int i = 0; i < N_; i++) {
mn = min(mn, T_[i]);
mx = max(mx, T_[i]);
prefMinT_[i] = mn;
prefMaxT_[i] = mx;
}
}
// sparse table for max on H
lg2_.assign(M_ + 1, 0);
for (int i = 2; i <= M_; i++) lg2_[i] = lg2_[i >> 1] + 1;
int K = lg2_[M_] + 1;
stMaxH_.assign(K, vector<int>(M_, 0));
stMaxH_[0] = H_;
for (int k = 1; k < K; k++) {
int half = 1 << (k - 1);
int span = 1 << k;
for (int i = 0; i + span <= M_; i++) {
stMaxH_[k][i] = max(stMaxH_[k - 1][i], stMaxH_[k - 1][i + half]);
}
}
// nearest strictly smaller on left (lf_)
lf_.assign(M_, -1);
{
vector<int> st;
st.reserve(M_);
for (int i = 0; i < M_; i++) {
while (!st.empty() && H_[st.back()] >= H_[i]) st.pop_back();
lf_[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
}
// nearest strictly smaller on right (rg_)
rg_.assign(M_, -1);
{
vector<int> st;
st.reserve(M_);
for (int i = M_ - 1; i >= 0; i--) {
while (!st.empty() && H_[st.back()] >= H_[i]) st.pop_back();
rg_[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
}
// Compute minVal_ in increasing order of humidity:
// minVal[u] = min(H[u], minVal[v]) for v in {lf[u],rg[u]} that are "jumpable" from u.
// Jump condition from u to v:
// bestTemp(H[u]) > max(H[min(u,v)..max(u,v)]).
minVal_.assign(M_, 0);
vector<int> ord(M_);
iota(ord.begin(), ord.end(), 0);
stable_sort(ord.begin(), ord.end(), [&](int a, int b) {
if (H_[a] != H_[b]) return H_[a] < H_[b];
return a < b;
});
for (int u : ord) {
int t = bestTemp(H_[u]);
int best = H_[u];
if (t != -1) {
int v = lf_[u];
if (v != -1 && t > rangeMaxH(u, v)) best = min(best, minVal_[v]);
v = rg_[u];
if (v != -1 && t > rangeMaxH(u, v)) best = min(best, minVal_[v]);
}
minVal_[u] = best;
}
// Final component id for each column u:
// t2 = bestTemp(minVal[u]), then component is the maximal interval containing u
// where all humidities < t2 (i.e. max on interval < t2).
compL_.assign(M_, 0);
compR_.assign(M_, 0);
for (int u = 0; u < M_; u++) {
int t2 = bestTemp(minVal_[u]);
if (t2 == -1) {
compL_[u] = compR_[u] = u;
} else {
compL_[u] = leftBoundary(u, t2);
compR_[u] = rightBoundary(u, t2);
}
}
}
bool can_reach(int /*L*/, int /*R*/, int S, int D) {
// L=0, R=M-1 always in this version.
return (compL_[S] == compL_[D] && compR_[S] == compR_[D]);
}
