#include <bits/stdc++.h>
using namespace std;
struct SegTree {
struct Node {
int mx; // maximum H in the segment
int mn; // minimum H in the segment
int mnPos; // position of the minimum (any)
};
int n;
vector<Node> st;
vector<int> *arrPtr; // pointer to original H array
SegTree() : n(0), arrPtr(nullptr) {}
void init(const vector<int> &arr) {
n = (int)arr.size();
arrPtr = const_cast<vector<int>*>(&arr);
st.assign(4 * n, Node());
build(1, 0, n - 1);
}
void build(int p, int l, int r) {
if (l == r) {
int val = (*arrPtr)[l];
st[p] = {val, val, l};
return;
}
int m = (l + r) >> 1;
build(p << 1, l, m);
build(p << 1 | 1, m + 1, r);
pull(p);
}
void pull(int p) {
const Node &L = st[p << 1];
const Node &R = st[p << 1 | 1];
st[p].mx = max(L.mx, R.mx);
if (L.mn <= R.mn) {
st[p].mn = L.mn;
st[p].mnPos = L.mnPos;
} else {
st[p].mn = R.mn;
st[p].mnPos = R.mnPos;
}
}
// range minimum query (value, position)
pair<int,int> queryMin(int p, int l, int r, int ql, int qr) const {
if (qr < l || ql > r) return {INT_MAX, -1};
if (ql <= l && r <= qr) return {st[p].mn, st[p].mnPos};
int m = (l + r) >> 1;
auto left = queryMin(p<<1, l, m, ql, qr);
auto right = queryMin(p<<1|1, m+1, r, ql, qr);
if (left.first <= right.first) return left;
return right;
}
// public wrapper
pair<int,int> rangeMin(int l, int r) const {
return queryMin(1, 0, n-1, l, r);
}
// find first index in [ql,qr] where H >= thr, returns n if none
int findFirstGE(int p, int l, int r, int ql, int qr, int thr) const {
if (qr < l || ql > r) return n;
if (st[p].mx < thr) return n;
if (l == r) return l;
int m = (l + r) >> 1;
int leftRes = findFirstGE(p<<1, l, m, ql, qr, thr);
if (leftRes != n) return leftRes;
return findFirstGE(p<<1|1, m+1, r, ql, qr, thr);
}
// find last index in [ql,qr] where H >= thr, returns -1 if none
int findLastGE(int p, int l, int r, int ql, int qr, int thr) const {
if (qr < l || ql > r) return -1;
if (st[p].mx < thr) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int rightRes = findLastGE(p<<1|1, m+1, r, ql, qr, thr);
if (rightRes != -1) return rightRes;
return findLastGE(p<<1, l, m, ql, qr, thr);
}
// wrappers
int firstGE(int l, int r, int thr) const {
if (l > r) return n;
return findFirstGE(1, 0, n-1, l, r, thr);
}
int lastGE(int l, int r, int thr) const {
if (l > r) return -1;
return findLastGE(1, 0, n-1, l, r, thr);
}
};
static vector<int> T_global;
static vector<int> H_global;
static vector<int> prefMaxT;
static SegTree seg;
static int N, M;
// compute deepest reachable row index starting from a given column position
static int computeDepth(int startPos) {
int curPos = startPos;
int curMin = H_global[curPos];
int depth = 0; // row 0 is always reachable
for (int i = 1; i < N; ++i) {
if (T_global[i] <= curMin) break; // cannot go down to this row
// expand the horizontal interval on row i starting from curPos
int leftBound = 0;
if (curPos > 0) {
int leftBlock = seg.lastGE(0, curPos - 1, T_global[i]);
if (leftBlock != -1) leftBound = leftBlock + 1;
}
int rightBound = M - 1;
if (curPos < M - 1) {
int rightBlock = seg.firstGE(curPos + 1, M - 1, T_global[i]);
if (rightBlock != M) rightBound = rightBlock - 1;
}
// query the minimum humidity inside the new interval
auto minInfo = seg.rangeMin(leftBound, rightBound);
curPos = minInfo.second;
curMin = minInfo.first;
depth = i;
}
return depth;
}
void initialize(vector<int> T, vector<int> H) {
T_global.swap(T);
H_global.swap(H);
N = (int)T_global.size();
M = (int)H_global.size();
prefMaxT.resize(N);
for (int i = 0; i < N; ++i) {
prefMaxT[i] = (i == 0) ? T_global[0] : max(prefMaxT[i-1], T_global[i]);
}
seg.init(H_global);
}
bool can_reach(int L, int R, int S, int D) {
// According to the sub‑task constraints L == 0 and R == M-1, so we ignore them.
if (S == D) return true;
// ------- max humidity on the whole column interval [min(S,D), max(S,D)] -------
int leftIdx = min(S, D);
int rightIdx = max(S, D);
int maxH = -1;
for (int i = leftIdx; i <= rightIdx; ++i) {
if (H_global[i] > maxH) maxH = H_global[i];
}
// ------- start interval on row 0 (containing S) -------
int Ls = S;
while (Ls > 0 && H_global[Ls - 1] < T_global[0]) --Ls;
int Rs = S;
while (Rs + 1 < M && H_global[Rs + 1] < T_global[0]) ++Rs;
auto startInfo = seg.rangeMin(Ls, Rs);
int startPos = startInfo.second;
int depthStart = computeDepth(startPos);
// ------- target interval on row 0 (containing D) -------
int Ld = D;
while (Ld > 0 && H_global[Ld - 1] < T_global[0]) --Ld;
int Rd = D;
while (Rd + 1 < M && H_global[Rd + 1] < T_global[0]) ++Rd;
auto targetInfo = seg.rangeMin(Ld, Rd);
int targetPos = targetInfo.second;
int depthTarget = computeDepth(targetPos);
int reachableDepth = min(depthStart, depthTarget);
int maxReachableTemp = prefMaxT[reachableDepth];
return maxReachableTemp > maxH;
}
