#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll hf(ll x, ll y){
return x*pow(10, 6)+y;
}
ll 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();
//for (int i=0; i<n; i++) h[i] = pow(10, 9);
int m = l.size();
vector<vector<int>> cp(m*2), ip(m);
vector<vector<int>> ev;
for (int i=0; i<m; i++){
ev.push_back({l[i], 1, i});
ev.push_back({r[i], -1, i});
}
set<int> hs;
map<int,int> htw;
sort(ev.begin(), ev.end());
int i = 0;
while (i < (int)ev.size()){
int ct = ev[i][0];
set<int> rm, in;
while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == -1){
hs.erase(y[ev[i][2]]);
rm.insert(ev[i][2]);
i++;
}
while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == 1){
hs.insert(y[ev[i][2]]);
htw[y[ev[i][2]]] = ev[i][2];
in.insert(ev[i][2]);
i++;
}
for (int w : rm){
auto it = hs.upper_bound(y[w]);
if (it != hs.end()) cp[w].push_back(htw[*it]);
if (it != hs.begin()){
it--;
cp[w].push_back(htw[*it]);
if (*it == y[w] && it != hs.begin()){
it--;
cp[w].push_back(htw[*it]);
}
}
}
for (int w : in){
auto it = hs.upper_bound(y[w]);
if (it != hs.end()) cp[w+m].push_back(htw[*it]);
if (it != hs.begin()){
it--;
if (*it == y[w] && it != hs.begin()){
it--;
cp[w+m].push_back(htw[*it]);
}
}
}
}
map<ll,vector<pair<ll,ll>>> gh;
for (int i=0; i<m; i++){
ip[i].push_back(l[i]);
ip[i].push_back(r[i]);
for (int next : cp[i]){
if (y[next] <= h[r[i]]) ip[next].push_back(r[i]);
}
for (int next : cp[i+m]){
assert(l[next] <= l[i] && l[i] <= r[next]);
if (y[next] <= h[l[i]]) ip[next].push_back(l[i]);
}
}
for (int i=0; i<m; i++){
if (l[i] <= s && s <= r[i] && y[i] <= h[s]) gh[hf(s, 0)].push_back({hf(s, y[i]), y[i]});
if (l[i] <= g && g <= r[i] && y[i] <= h[g]) gh[hf(g, y[i])].push_back({hf(g, 0), y[i]});
sort(ip[i].begin(), ip[i].end());
assert(ip[i][0] == l[i] && ip[i].back() == r[i]);
for (int j=0; j+1<(int)ip[i].size(); j++){
gh[hf(ip[i][j], y[i])].push_back({hf(ip[i][j+1], y[i]), x[ip[i][j+1]]-x[ip[i][j]]});
gh[hf(ip[i][j+1], y[i])].push_back({hf(ip[i][j], y[i]), x[ip[i][j+1]]-x[ip[i][j]]});
}
for (int next : cp[i]){
if (y[next] > h[r[i]]) continue;
gh[hf(r[i], y[i])].push_back({hf(r[i], y[next]), abs(y[next]-y[i])});
gh[hf(r[i], y[next])].push_back({hf(r[i], y[i]), abs(y[next]-y[i])});
}
/*for (int next : cp[i+m]){
if (y[next] > h[l[i]]) continue;
gh[hf(l[i], y[i])].push_back({hf(l[i], y[next]), abs(y[next]-y[i])});
gh[hf(l[i], y[next])].push_back({hf(l[i], y[i]), abs(y[next]-y[i])});
}*/
}
priority_queue<pair<ll,ll>> pq;
pq.push({0, hf(s, 0)});
unordered_set<ll> seen;
while (!pq.empty()){
ll cur = pq.top().second, d = -pq.top().first;
pq.pop();
if (seen.find(cur) != seen.end()) continue;
seen.insert(cur);
if (cur == hf(g, 0)) return d;
for (pair<ll,ll> next : gh[cur]) pq.push({-(d+next.second), next.first});
}
return -1;
}
