#include "walk.h"
#include <map>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
map < pair < long long , long long > , vector < pair < long long , pair < long long , long long > > > > Next;
priority_queue < pair < long long , pair < long long , long long > > , vector < pair < long long , pair < long long , long long > > > , greater < pair < long long , pair < long long , long long > > > > all;
set < pair < long long , long long> > have;
vector < long long > xx[500005];
vector < long long > yy[500005];
bool F(long long a,long long b)
{
return a<b;
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g)
{
long long N=(long long) x.size(),M=(long long) l.size(),t,i,j;
for(i=0;i<N;i++)
{
xx[i].push_back(0);
xx[i].push_back(h[i]);
}
for(i=0;i<M;i++)
{
yy[i].push_back(l[i]);
yy[i].push_back(r[i]);
}
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
if(l[j]<=x[i]&&x[i]<=r[j]&&y[j]<=h[i])
{
xx[i].push_back(y[j]);
yy[j].push_back(x[i]);
}
}
}
for(i=0;i<N;i++)
{
sort(xx[i].begin(),xx[i].end(),F);
t=(long long) xx[i].size();
for(j=1;j<t;j++)
{
Next[make_pair(x[i],xx[i][j-1])].push_back(make_pair(xx[i][j]-xx[i][j-1],make_pair(x[i],xx[i][j])));
Next[make_pair(x[i],xx[i][j])].push_back(make_pair(xx[i][j]-xx[i][j-1],make_pair(x[i],xx[i][j-1])));
}
}
for(i=0;i<M;i++)
{
sort(yy[i].begin(),yy[i].end(),F);
t=(long long) yy[i].size();
for(j=1;j<t;j++)
{
Next[make_pair(yy[i][j-1],y[i])].push_back(make_pair(yy[i][j]-yy[i][j-1],make_pair(yy[i][j],y[i])));
Next[make_pair(yy[i][j],y[i])].push_back(make_pair(yy[i][j]-yy[i][j-1],make_pair(yy[i][j-1],y[i])));
}
}
all.push(make_pair((long long)0,make_pair((long long)s,(long long)0)));
while(!all.empty())
{
auto xx=all.top();
all.pop();
if(xx.second==make_pair((long long) g,(long long)0)) return xx.first;
if(have.find(xx.second)!=have.end()) continue;
for(auto i:Next[xx.second]) all.push(make_pair(xx.first+i.first,i.second));
}
return -1;
}
