#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<pii> se;
vector<pii> 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<int> hs[MAX];
vector<int> xs[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],i}),S[R[i]].push_back({Y[i],i});
for (int i=0;i<N;i++){
for (auto [a,ei]:E[i]){
se.erase({a,ei});
auto it=se.lower_bound({a,-1});
if (it!=se.end()&&it->first<=H[i]) hs[i].push_back(it->first),xs[it->second].push_back(i);
if (it!=se.begin()) hs[i].push_back(prev(it)->first),xs[prev(it)->second].push_back(i);
hs[i].push_back(a);
xs[ei].push_back(i);
}
for (auto [a,ei]:S[i]){
auto it=se.lower_bound({a,-1});
if (it!=se.end()&&it->first<=H[i]) hs[i].push_back(it->first),xs[it->second].push_back(i);
if (it!=se.begin()) hs[i].push_back(prev(it)->first),xs[prev(it)->second].push_back(i);
hs[i].push_back(a);
xs[ei].push_back(i);
se.insert({a,ei});
}
}
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++) sort(xs[i].begin(),xs[i].end()),xs[i].resize(unique(xs[i].begin(),xs[i].end())-xs[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++) for (int j=0;j<(int)xs[i].size()-1;j++){
int ai=xs[i][j],bi=xs[i][j+1];
pii a={ai,lower_bound(hs[ai].begin(),hs[ai].end(),Y[i])-hs[ai].begin()};
pii b={bi,lower_bound(hs[bi].begin(),hs[bi].end(),Y[i])-hs[bi].begin()};
ll w=X[bi]-X[ai];
adj[idx(a)].push_back({w,idx(b)}),adj[idx(b)].push_back({w,idx(a)});
}
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;
}
