/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┗━┓ ┏━┛ + +
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the llama protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
//thanks cindy
// should've ac'd in contest
#include "obstacles.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
// T[i] > H[i] means no obstacle, T[i] <= H[i] means obstacle
// Note: N is #columns, M is #rows, reversed from problem statement
ll N, M, logN = 23;
vector<ll> T, H;
char *_BRK;
void *galloc(ll sz) {
auto out = (void *)_BRK;
_BRK += sz;
return out;
}
struct plist {
ll v;
plist *r;
plist (ll gay) {
v = gay;
r = nullptr;
}
};
struct pvec {
plist *l, *r;
pvec (){
l = r = nullptr;
}
};
struct snode {
ll l, r, vi, va;
snode *lc, *rc;
void construct(vector<ll> &gay) {
if (l == r) {
vi = va = gay[l];
return;
}
lc = (snode*)(malloc(sizeof(snode)));
rc = (snode*)(malloc(sizeof(snode)));
lc -> l = l;
rc -> r = r;
lc -> r = floor((l+r)/2.0);
rc -> l = lc -> r + 1;
lc -> construct(gay);
rc -> construct(gay);
vi = min(lc -> vi, rc -> vi);
va = max(lc -> va, rc -> va);
}
ll qmin(ll li, ll ri){
if (li == l && ri == r) return vi;
ll output = 1e18;
if (li <= lc -> r) output = lc -> qmin(li, min(ri, lc -> r));
if (ri >= rc -> l) output = min(output, rc -> qmin(max(li, rc -> l), ri));
return output;
}
ll qmax(ll li, ll ri){
if (li == l && ri == r) return va;
ll output = -1e18;
if (li <= lc -> r) output = lc -> qmax(li, min(ri, lc -> r));
if (ri >= rc -> l) output = max(output, rc -> qmax(max(li, rc -> l), ri));
return output;
}
pvec* qhum(ll li, ll ri, ll val){ // returns a sorted linked list on postions >= val
pvec *out;
out = (pvec*)(malloc(sizeof(pvec)));
if (va < val) {
out -> l = out -> r = nullptr;
return out;
}
if (l == r) {
out -> l = out -> r = (plist*)(malloc(sizeof(plist)));
out -> l -> v = li;
out -> r -> r = nullptr;
return out;
}
if (li <= lc -> r) {
free(out);
out = lc -> qhum(li, min(lc -> r, ri), val);
if (ri >= rc -> l){
if (out -> l == nullptr) {
free(out);
return rc -> qhum(max(li, rc -> l), ri, val);
}
auto p = rc -> qhum(max(li, rc -> l), ri, val);
if (p -> l != nullptr) out -> r -> r = p -> l;
if (p -> l != nullptr) out -> r = p -> r;
free(p);
}
return out;
}
else {
free(out);
return rc -> qhum(li, ri, val);
}
}
ll qtemp(ll li, ll ri, ll val) { // find the first position > val, or return -69
if (l == r) {
if (va <= val) return -69;
else return l;
}
if (va <= val) return -69;
ll output = -69;
if (li <= lc -> r) output = lc -> qtemp(li, min(ri, lc -> r), val);
if (output == -69){
if (ri >= rc -> l) output = rc -> qtemp(max(li, rc -> l), ri, val);
}
return output;
}
ll qhl(ll li, ll ri, ll val) { // find the first position < val, or return -69
if (l == r) {
if (vi >= val) return -69;
else return l;
}
if (vi >= val) return -69;
ll output = -69;
if (li <= lc -> r) output = lc -> qhl(li, min(ri, lc -> r), val);
if (output == -69){
if (ri >= rc -> l) output = rc -> qhl(max(li, rc -> l), ri, val);
}
return output;
}
ll qhr(ll li, ll ri, ll val) { // find the last position < val, or return -69
if (l == r) {
if (vi >= val) return -69;
else return l;
}
if (vi >= val) return -69;
ll output = -69;
if (ri >= rc -> l) output = rc -> qhr(max(li, rc -> l), ri, val);
if (output == -69){
if (li <= lc -> r) output = lc -> qhr(li, min(ri, lc -> r), val);
}
return output;
}
};
snode rootn, rootm;
class tnode;
struct Lca { // To pass, left <= l, right >= r
tnode *pos;
ll l, r;
Lca(){}
Lca (Lca a, Lca b){ // Combines ancestor to descendent
l = min(a.l, b.l);
r = max(a.r, b.r);
pos = a.pos;
}
Lca (tnode *a, ll b, ll c){ // Make a boring object lol
pos = a;
l = b;
r = c;
}
};
ll adjust (ll a, ll b) {
if (a == -69) return b;
return a;
}
struct tnode{
ll l, r,h, th, pl, pr; // l, r for range, h for y value, th for tree height,
//pl pr for Lca object parent pointer
vector<tnode*> ch; // list of children pointers
vector<Lca> lca; // LCA construct
tnode *par; // parent pointer
void build (vector<tnode*> &Lea, bool _indicator = true) {
// do the LCA shit here
ch = vector<tnode*>(0);
if ( l==53701 || l == 105895) {
int asdfas = 0;
asdfas ++;
}
if (_indicator) {
lca = vector<Lca>(0);
lca = vector<Lca> (logN);
lca[0] = Lca(par, pl, pr);
for (ll i = 1; i < logN; i++) {
lca[i] = Lca(lca[i-1].pos -> lca[i-1], lca[i-1]);
}
}
if (h == 0) {
for (ll i = l; i <= r; i++) Lea[i] = this;
return;
}
ll Ta = rootm.qmax(0, h-1);
pvec *X = rootn.qhum(l, r, Ta);
plist *lll, *rrr;
lll = (plist*)(malloc(sizeof(plist)));
rrr = (plist*)(malloc(sizeof(plist)));
*lll = plist(l-1);
*rrr = plist(r + 1);
lll -> r = X -> l;
X -> l = lll;
if (X -> r == nullptr) X -> r = lll;
X -> r -> r = rrr;
X -> r = rrr;
for (plist *i = X -> l; i -> r != nullptr; i = i -> r){
if (i -> r -> v - i -> v <= 1) continue;
ch.push_back((tnode*)(galloc(sizeof(tnode))));
ch.back() -> l = i -> v + 1;
ch.back() -> r = i -> r -> v - 1;
ch.back() -> th = th + 1;
ch.back() -> par = this;
// now find height, pl, pr
ll pe = rootn.qmax(ch.back() -> l, ch.back() -> r);
ch.back() -> h = rootm.qtemp(0, h - 1, pe);
pe = rootm.qmin(ch.back() -> h, h - 1);
if (_indicator){
ch.back() -> pl = rootn.qhr(ch.back() -> l, ch.back() -> r, pe);
ch.back() -> pr = adjust(rootn.qhl(ch.back() -> l, ch.back() -> r, pe), N+M+5);
}
else {
ch.back() -> pl = -69;
ch.back() -> pr = N+M+5;
}
ch.back() -> build(Lea);
}
}
};
Lca trace(tnode *a, tnode *b){
if (a -> th < b -> th) {
auto c = a;
a = b;
b = c;
}
Lca A(a, N+1, -1), B(b, N+1, -1);
for (ll i = logN-1; i >= 0; i--){
if (a -> lca[i].pos -> th >= b -> th){
A = Lca(a -> lca[i], A);
a = A.pos;
}
}
if (a != b) {
for (ll i = logN-1; i >= 0; i--){
if (a -> lca[i].pos != b -> lca[i].pos){
A = Lca(a -> lca[i], A);
a = A.pos;
B = Lca(b -> lca[i], B);
b = B.pos;
}
}
A = Lca(a -> lca[0], A);
a = A.pos;
B = Lca(b -> lca[0], B);
b = B.pos;
}
A = Lca(A, B);
return A;
}
vector<tnode*> Leaf;
tnode gayroot;
void initialize(std::vector<int> t, std::vector<int> h) {
_BRK = (char*)malloc(sizeof(tnode) * 1e6);
N = h.size();
M = t.size();
T = vector<ll>(M);
H = vector<ll>(N);
Leaf = vector<tnode*> (N, nullptr);
for (ll i = 0; i < N; i++) H[i] = h[i];
for (ll i = 0; i < M; i++) T[i] = t[i];
rootn.l = rootm.l = 0;
rootn.r = N-1;
rootm.r = M-1;
rootn.construct(H);
rootm.construct(T);
gayroot.l = 0;
gayroot.r = N-1;
gayroot.lca = vector<Lca>(logN, Lca(&gayroot, N+1, -1));
gayroot.pl = -1;
gayroot.pr = N;
gayroot.h = M;
gayroot.th = 0;
gayroot.build(Leaf, false);
return;
}
bool can_reach(int L, int R, int S, int D) {
ll l = L, r = R, a = S, b = D;
if (Leaf[a] == nullptr || Leaf[b] == nullptr) return false;
//return Leaf[a] == Leaf[b];
auto P = trace(Leaf[a], Leaf[b]);
return (l <= P.l) && (r >= P.r);
}
