// Solution for the "Llama Path" problem.
// The grid is defined by row temperatures T[i] and column humidities H[j].
// A cell (i,j) is free iff T[i] > H[j].
// For each query we need to decide whether (0,S) can reach (0,D) staying
// inside free cells. Both S and D are guaranteed to be free at row 0.
#include <bits/stdc++.h>
using namespace std;
// ---------------------------------------------------------------------
// Global data filled by `initialize` and used by `can_reach`
// ---------------------------------------------------------------------
static vector<int> T_glob; // temperatures of rows
static vector<int> H_glob; // humidities of columns
static int maxReachableTemp; // maximum temperature among rows
// that are reachable from row 0
static struct SegTree {
int n = 0;
vector<int> seg; // iterative segment tree for range max
void init(const vector<int>& a) {
n = (int)a.size();
seg.assign(2 * n, INT_MIN);
for (int i = 0; i < n; ++i) seg[n + i] = a[i];
for (int i = n - 1; i > 0; --i) seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
// inclusive query on [l, r]
int query(int l, int r) const {
int res = INT_MIN;
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (!(r & 1)) res = max(res, seg[r--]);
}
return res;
}
} Hseg;
// ---------------------------------------------------------------------
// Initialization: runs once per test case
// ---------------------------------------------------------------------
void initialize(vector<int> T, vector<int> H) {
T_glob = std::move(T);
H_glob = std::move(H);
int N = (int)T_glob.size();
int M = (int)H_glob.size();
// Minimum humidity over all columns.
int Hmin = *min_element(H_glob.begin(), H_glob.end());
// Find the first row (index > 0) that has no free cell at all.
// A row i is completely blocked iff T[i] <= Hmin.
int firstDead = N; // N means "no dead row"
maxReachableTemp = T_glob[0]; // start with row 0
for (int i = 1; i < N; ++i) {
if (T_glob[i] <= Hmin) { // this row cannot be entered
firstDead = i;
break;
}
if (T_glob[i] > maxReachableTemp) maxReachableTemp = T_glob[i];
}
// If there is no dead row, the loop visited all rows and maxReachableTemp
// already equals the global maximum temperature.
// Build a segment tree on the humidity array for range‑maximum queries.
Hseg.init(H_glob);
}
// ---------------------------------------------------------------------
// Query: is there a valid path from (0,S) to (0,D) staying inside columns [L,R]?
// In the problem L = 0 and R = M‑1, so we only need to look at the columns
// between S and D.
// ---------------------------------------------------------------------
bool can_reach(int L, int R, int S, int D) {
// The interval we must cross on the top row.
int left = min(S, D);
int right = max(S, D);
// Maximum humidity among the columns we must cross.
int maxH = Hseg.query(left, right);
// Reachable iff every column in the interval has humidity < maxReachableTemp.
// Columns with humidity >= maxReachableTemp are completely blocked in the
// reachable part of the grid (they have no free cell in any row we can ever
// reach from the top).
return maxH < maxReachableTemp;
}
