#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e){
ll n=x.size(), m=l.size();
map<pair<ll,ll>,vector<pair<ll,ll>>> g;
vector<ll> x1[n], x2[n];
for(ll i=0; i<m; i++){
x1[l[i]].push_back(i);
x2[r[i]].push_back(i);
}
set<pair<ll,ll>> s1, s2;
for(ll i=0; i<n; i++){
for(auto j:x1[i]){
s1.insert({y[j],j});
s2.insert({-y[j],j});
if(i==0) g[{0,x[0]}].push_back({y[j],x[r[j]]});
}
for(auto j:x2[i]){
s1.erase({y[j],j});
s2.erase({-y[j],j});
if(i==n-1) g[{y[j],x[n-1]}].push_back({0,x[n-1]});
}
for(auto j:x2[i]){
ll nxt=(*s1.lower_bound({y[j],j})).second;
g[{y[j],x[i]}].push_back({y[nxt],x[r[nxt]]});
nxt=(*s2.upper_bound({-y[j],j})).second;
g[{y[j],x[i]}].push_back({y[nxt],x[r[nxt]]});
}
}
map<pair<ll,ll>,ll> dist; dist[{0,x[s]}]=0;
map<pair<ll,ll>,bool> vis;
priority_queue<pair<ll,pair<ll,ll>>> q; q.push({0,{0,x[s]}});
while(!q.empty()){
pair<ll,ll> curr=q.top().second;
q.pop();
if(vis[curr]) continue;
vis[curr]=1;
// cout<<curr.first<<" "<<curr.second<<" "<<dist[curr]<<endl;
for(auto nxt:g[curr]){
ll y=abs(curr.first-nxt.first)+abs(curr.second-nxt.second);
if(dist.find(nxt)==dist.end() || dist[nxt]>dist[curr]+y){
dist[nxt]=dist[curr]+y;
q.push({-dist[nxt],nxt});
}
}
}
// cout<<vis[{0,x[e]}]<<endl;
pair<ll,ll> z={0,x[e]};
if(vis[z]) return dist[{0,x[e]}];
else return -1;
}
