#include <bits/stdc++.h>
using namespace std;
/* Global data filled by initialize */
static vector<int> Trow; // temperature per row
static vector<int> Hcol; // humidity per column
static int N, M;
static vector<int> Lbound, Rbound; // leftmost/rightmost free column of the interval containing a column (row 0)
static vector<int> prefMin, prefMax; // prefix minimum and maximum of Trow
static struct SegTree {
int n;
vector<int> mn, mx; // range minimum and maximum of Hcol
SegTree() {}
explicit SegTree(const vector<int>& a) {
n = (int)a.size();
mn.assign(4 * n, INT_MAX);
mx.assign(4 * n, INT_MIN);
build(1, 0, n - 1, a);
}
void build(int v, int l, int r, const vector<int>& a) {
if (l == r) {
mn[v] = mx[v] = a[l];
return;
}
int m = (l + r) >> 1;
build(v << 1, l, m, a);
build(v << 1 | 1, m + 1, r, a);
mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}
int queryMin(int L, int R) const { return queryMin(1, 0, n - 1, L, R); }
int queryMax(int L, int R) const { return queryMax(1, 0, n - 1, L, R); }
int queryMin(int v, int l, int r, int L, int R) const {
if (R < l || r < L) return INT_MAX;
if (L <= l && r <= R) return mn[v];
int m = (l + r) >> 1;
return min(queryMin(v << 1, l, m, L, R),
queryMin(v << 1 | 1, m + 1, r, L, R));
}
int queryMax(int v, int l, int r, int L, int R) const {
if (R < l || r < L) return INT_MIN;
if (L <= l && r <= R) return mx[v];
int m = (l + r) >> 1;
return max(queryMax(v << 1, l, m, L, R),
queryMax(v << 1 | 1, m + 1, r, L, R));
}
} segH;
/* Pre‑processing */
void initialize(vector<int> T, vector<int> H) {
Trow = move(T);
Hcol = move(H);
N = (int)Trow.size();
M = (int)Hcol.size();
int T0 = Trow[0];
vector<char> free0(M, 0);
for (int j = 0; j < M; ++j) {
free0[j] = (Hcol[j] < T0);
}
Lbound.assign(M, -1);
Rbound.assign(M, -1);
int curL = -1;
for (int j = 0; j < M; ++j) {
if (free0[j]) {
if (curL == -1) curL = j;
Lbound[j] = curL;
} else {
curL = -1;
}
}
int curR = -1;
for (int j = M - 1; j >= 0; --j) {
if (free0[j]) {
if (curR == -1) curR = j;
Rbound[j] = curR;
} else {
curR = -1;
}
}
prefMin.assign(N, 0);
prefMax.assign(N, 0);
for (int i = 0; i < N; ++i) {
if (i == 0) {
prefMin[i] = Trow[i];
prefMax[i] = Trow[i];
} else {
prefMin[i] = min(prefMin[i - 1], Trow[i]);
prefMax[i] = max(prefMax[i - 1], Trow[i]);
}
}
segH = SegTree(Hcol);
}
/* Query */
bool can_reach(int L, int R, int S, int D) {
(void)L; (void)R; // L,R are always 0 and M‑1 in the sub‑problem
if (S == D) return true;
int leftS = Lbound[S];
int rightS = Rbound[S]; // S is guaranteed to be free, so these are valid
// same free interval on row 0 ?
if (leftS <= D && D <= rightS) return true;
// determine the columns that must be crossed horizontally
int crossL, crossR;
if (D > rightS) { // D is to the right of S's interval
crossL = rightS;
crossR = D;
} else { // D is to the left
crossL = D;
crossR = leftS;
}
int maxHumCross = segH.queryMax(crossL, crossR);
int minHumS = segH.queryMin(leftS, rightS);
int leftD = Lbound[D];
int rightD = Rbound[D];
int minHumD = segH.queryMin(leftD, rightD);
int combinedMinH = max(minHumS, minHumD); // must be strictly smaller than all rows we descend through
// largest index i with prefMin[i] > combinedMinH
int lo = 0, hi = N - 1, i_limit = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (prefMin[mid] > combinedMinH) {
i_limit = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
// required temperature to be able to cross the horizontal segment
int required = max(minHumS, maxHumCross);
// there must be a row (with index <= i_limit) whose temperature exceeds 'required'
return prefMax[i_limit] > required;
}
