#include "walk.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
vector <int> a[100001],b[100001],V;
vector <pair <int, int>> ke[12000001],ve,nodes;
int n,m,d[12000001],dp[200001],ft[200001][2];
set <int> S;
void add(int i, int j){
a[i].push_back(j);
nodes.push_back({i,j});
}
int f(int i, int j){
return lower_bound(nodes.begin(),nodes.end(),make_pair(i,j))-nodes.begin();
}
void update(int i, int j, int val){
for (;i<=V.size();i+=i&(-i))
ft[i][j]=min(ft[i][j],val);
}
int get(int i, int j){
int res=INF;
for (;i;i-=i&(-i))
res=min(res,ft[i][j]);
return res;
}
int min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g){
n=x.size(),m=l.size();
int ch=1;
for (int i=1;i<n;i++)
ch&=(h[i]==h[0]);
if (s>g)
swap(s,g);
if (s==0&&g==n-1&&ch){
vector <pair <int, int>> tmp;
for (int i=0;i<m;i++){
tmp.push_back({l[i],r[i]});
ve.push_back({l[i],y[i]});
if (r[i]==g)
ve.push_back({r[i],y[i]});
}
sort(tmp.begin(),tmp.end());
int cur=0;
for (auto [i,j]:tmp)
if (cur>=i)
cur=max(cur,j);
if (cur<g)
return -1;
sort(ve.begin(),ve.end());
for (auto [i,j]:ve)
V.push_back(j);
sort(V.begin(),V.end());
V.resize(unique(V.begin(),V.end())-V.begin());
for (int i=0;i<=V.size();i++)
ft[i][0]=ft[i][1]=INF;
for (int i=ve.size()-1;i>=0;i--){
int Y=ve[i].second,j=lower_bound(V.begin(),V.end(),Y)-V.begin()+1;
if (ve[i].first==g)
dp[i]=Y;
else
dp[i]=min(get(V.size()-j+1,0)-Y,get(j,1)+Y);
update(V.size()-j+1,0,dp[i]+Y);
update(j,1,dp[i]-Y);
}
return dp[0]+ve[0].second+x[g]-x[s];
}
for (int i=0;i<n;i++)
ve.push_back({-h[i],-i});
for (int i=0;i<m;i++)
ve.push_back({-y[i],i+1});
sort(ve.begin(),ve.end());
for (auto [i,j]:ve){
i=-i,j=-j;
if (j>=0){
S.insert(j);
continue;
}
j=-j-1;
for (auto it=S.lower_bound(l[j]);it!=S.end()&&*it<=r[j];it++){
add(*it,j);
b[j].push_back(*it);
}
}
add(s,-1);
add(g,-1);
sort(nodes.begin(),nodes.end());
nodes.resize(unique(nodes.begin(),nodes.end())-nodes.begin());
for (int i=0;i<n;i++)
for (int j=0;j<(int)a[i].size()-1;j++){
int u=f(i,a[i][j]),v=f(i,a[i][j+1]),w=abs((a[i][j]>=0?y[a[i][j]]:0)-(a[i][j+1]>=0?y[a[i][j+1]]:0));
ke[u].push_back({v,w});
ke[v].push_back({u,w});
}
for (int i=0;i<m;i++)
for (int j=0;j<(int)b[i].size()-1;j++){
int u=f(b[i][j],i),v=f(b[i][j+1],i),w=x[b[i][j+1]]-x[b[i][j]];
ke[u].push_back({v,w});
ke[v].push_back({u,w});
}
fill(d,d+nodes.size(),INF);
d[f(s,-1)]=0;
q.push({0,f(s,-1)});
while (!q.empty()){
auto [du,u]=q.top();
q.pop();
if (du!=d[u])
continue;
for (auto [v,w]:ke[u])
if (d[v]>d[u]+w){
d[v]=d[u]+w;
q.push({d[v],v});
}
}
return (d[f(g,-1)]==INF?-1:d[f(g,-1)]);
}
