#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e6 + 9;
const ll inf = 1e18;
vector<pair<int,int>> nei[M];
ll dis[M];
ll dj()
{
for (int i=0;i<M;i++) dis[i]=inf;
dis[0]=0;
set<pair<ll,int>> se;
se.insert({0,0});
while (se.size())
{
auto p=*se.begin();se.erase(se.begin());
for (auto [i,d]:nei[p.second])
if (dis[i]>p.first+d)
{
se.erase({dis[i],i});
dis[i]=p.first+d;
se.insert({dis[i],i});
}
}
if (dis[1]==inf) dis[1]=-1;
return dis[1];
}
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=x.size(), m=l.size();
map<pair<int,int>,int> ind;
ind[{s,0}]=0, ind[{g,0}]=1;
vector<pair<int,int>> v;
vector<int> ins[n], ins1[m];
ins[s]=ins[g]={0};
for (int i=0;i<n;i++)
v.push_back({h[i],i+m});
for (int i=0;i<m;i++)
v.push_back({y[i],i});
sort(v.rbegin(),v.rend());
set<int> se;
for (auto [a,b]:v)
{
if (b<m)
{
auto it=se.lower_bound(l[b]);
while (1)
{
int i=*it;
if (ind.find({i,a})==ind.end())
ind[{i,a}]=ind.size();
ins[i].push_back(a), ins1[b].push_back(i);
if (i==r[b]) break;
it++;
}
}
else
se.insert(b-m);
}
for (int i=0;i<n;i++)
{
sort(ins[i].begin(),ins[i].end());
for (int j=0;j+1<ins[i].size();j++)
nei[ind[{i,ins[i][j]}]].push_back({ind[{i,ins[i][j+1]}],ins[i][j+1]-ins[i][j]}),
nei[ind[{i,ins[i][j+1]}]].push_back({ind[{i,ins[i][j]}],ins[i][j+1]-ins[i][j]});
}
for (int i=0;i<m;i++)
{
for (int j=0;j+1<ins1[i].size();j++)
nei[ind[{ins1[i][j],y[i]}]].push_back({ind[{ins1[i][j+1],y[i]}],x[ins1[i][j+1]]-x[ins1[i][j]]}),
nei[ind[{ins1[i][j+1],y[i]}]].push_back({ind[{ins1[i][j],y[i]}],x[ins1[i][j+1]]-x[ins1[i][j]]});
}
return dj();
}
