#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
int to_x,to_y;
int dist;
};
vector<int>node[100000];
vector<vector<edge>>e[100000];
vector<long long>dist[100000];
long long min_distance(vector<int>x,vector<int>h,vector<int>l,vector<int>r,vector<int>y,int s,int g){
int N,M;
N=x.size();
M=l.size();
for(int i=0;i<N;i++){
node[i].push_back(0);
node[i].push_back(h[i]);
}
set<int>st;
priority_queue<pair<int,pair<int,int>>>que;
for(int i=0;i<N;i++){
que.push({h[i],{1,i}});
}
for(int i=0;i<M;i++){
que.push({y[i],{0,i}});
}
while(!que.empty()){
int height,type,id;
height=que.top().first;
type=que.top().second.first;
id=que.top().second.second;
que.pop();
if(type){
st.insert(id);
}
else{
auto it=st.lower_bound(l[id]);
while(true){
node[*it].push_back(y[id]);
if(*it==r[id])break;
it++;
}
}
}
for(int i=0;i<N;i++){
sort(node[i].begin(),node[i].end());
node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
dist[i]=vector<long long>(node[i].size(),-1);
e[i]=vector<vector<edge>>(node[i].size());
for(int j=0;j<node[i].size()-1;j++){
e[i][j].push_back({i,j+1,node[i][j+1]-node[i][j]});
e[i][j+1].push_back({i,j,node[i][j+1]-node[i][j]});
}
}
st.clear();
for(int i=0;i<N;i++){
que.push({h[i],{1,i}});
}
for(int i=0;i<M;i++){
que.push({y[i],{0,i}});
}
while(!que.empty()){
int height,type,id;
height=que.top().first;
type=que.top().second.first;
id=que.top().second.second;
que.pop();
if(type){
st.insert(id);
}
else{
auto it=st.lower_bound(l[id]);
vector<pair<int,int>>p;
while(true){
p.push_back({*it,lower_bound(node[*it].begin(),node[*it].end(),y[id])-node[*it].begin()});
if(*it==r[id])break;
it++;
}
for(int j=0;j<p.size()-1;j++){
e[p[j].first][p[j].second].push_back({p[j+1].first,p[j+1].second,x[p[j+1].first]-x[p[j].first]});
e[p[j+1].first][p[j+1].second].push_back({p[j].first,p[j].second,x[p[j+1].first]-x[p[j].first]});
}
}
}
priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>>pq;
pq.push({0,{s,0}});
while(!pq.empty()){
long long l;
int px;
int py;
l=pq.top().first;
px=pq.top().second.first;
py=pq.top().second.second;
pq.pop();
if(dist[px][py]==-1){
dist[px][py]=l;
for(edge E:e[px][py]){
pq.push({l+E.dist,{E.to_x,E.to_y}});
}
}
}
return dist[g][0];
}
