#include "walk.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
using namespace std;
const int MAX=6e5+5;
const ll INF=1LL<<60;
int N,M;
set<int> se;
vector<int> S[MAX],E[MAX];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>> pq;
vector<pii> disc;
ll dst[MAX];
vector<pair<ll,int>> adj[MAX];
vector<ll> hs[MAX];
inline int idx(pii a){
return lower_bound(disc.begin(),disc.end(),a)-disc.begin();
}
long long min_distance(vector<int> X,vector<int> H,vector<int> L,vector<int> R,vector<int> Y,int s,int g) {
N=X.size(),M=L.size();
for (int i=0;i<M;i++) S[L[i]].push_back(Y[i]),S[R[i]].push_back(Y[i]);
for (int i=0;i<N;i++){
for (auto a:E[i]){
se.erase(a);
auto it=se.lower_bound(a);
if (it!=se.end()) hs[i].push_back(*it);
if (it!=se.begin()) hs[i].push_back(*prev(it));
}
for (auto a:S[i]){
auto it=se.lower_bound(a);
if (it!=se.end()) hs[i].push_back(*it);
if (it!=se.begin()) hs[i].push_back(*prev(it));
se.insert(a);
}
}
hs[s].push_back(0),hs[g].push_back(0);
for (int i=0;i<N;i++) sort(hs[i].begin(),hs[i].end()),hs[i].resize(unique(hs[i].begin(),hs[i].end())-hs[i].begin());
for (int i=0;i<N;i++) for (int x=0;x<hs[i].size();x++) disc.push_back({i,x});
sort(disc.begin(),disc.end());
int K=disc.size();
for (int i=0;i<N;i++) for (int x=0;x<(int)hs[i].size()-1;x++){
pii a={i,x};
pii b={i,x+1};
ll w=hs[i][x+1]-hs[i][x];
adj[idx(a)].push_back({w,idx(b)}),adj[idx(b)].push_back({w,idx(a)});
}
for (int i=0;i<M;i++){
int pi=L[i];
int p=lower_bound(hs[L[i]].begin(),hs[L[i]].end(),Y[i])-hs[L[i]].begin();
for (int x=L[i]+1;x<=R[i];x++){
int j=lower_bound(hs[x].begin(),hs[x].end(),Y[i])-hs[x].begin();
if (j<hs[x].size()){
pii a={pi,p};
pii b={x,j};
ll w=X[x]-X[pi];
adj[idx(a)].push_back({w,idx(b)}),adj[idx(b)].push_back({w,idx(a)});
p=j;
pi=x;
}
}
}
fill_n(dst,K,INF);
pq.push({0,idx({s,0})});
while (pq.size()){
auto [d,pr]=pq.top();
pq.pop();
if (d>=dst[pr]) continue;
dst[pr]=d;
for (auto [w,qr]:adj[pr]){
pq.push({d+w,qr});
}
}
ll ans=dst[idx({g,0})];
if (ans==INF) return -1;
return ans;
}
