#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
const int N=1e5+5;
const ll inp=1e18;
ll dist[N<<2];
vector<pair<int,int>> ma[N<<2];
ll min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g) {
if (s>g)swap(s,g);
// s<g
// solving s==1 and g==n-1
n=x.size(),q=l.size();
for (int j=0;j<2*q;j++) {
ma[j].clear();
}
for(int i=0;i<q;i++)
{
ma[2*i].push_back({x[r[i]]-x[l[i]],2*i+1});
ma[2*i+1].push_back({x[r[i]]-x[l[i]],2*i});
for(int j=0;j<q;j++)
{
// if(max(l[i],l[j])<=min(r[i],r[j]))
if(l[j]<=r[i] and r[i]<=r[j])
{
// intersection
if(abs(x[r[j]]-x[r[i]]) + abs(y[j]-y[i]) > 0)
{
// if(i==2)
{
// cout<<"weight "<<x[r[j]]-x[r[i]]<<' '<<y[j]-y[i]<<' '<<2*j+1<<' '<<l[j]<<' '<<r[j]<<' '<<y[j]<<endl;
}
ma[2*i+1].push_back({abs(x[r[j]]-x[r[i]]) + abs(y[j]-y[i]),2*j+1});
ma[2*j+1].push_back({abs(x[r[j]]-x[r[i]]) + abs(y[j]-y[i]),2*i+1});
}
}
}
}
// 0 for bottom on first building
// 2*q for bottom on last building
// for (int i=0;i<q;i++) {
// // node 2*i and 2*i-1
// ma[2*i].push_back({x[r[i]]-x[l[i]],2*i+1});
// auto cp=upper_bound(l[i],y[i]);
// if (cp.first!=inf) {
// int j=cp.second;
// ma[2*i].push_back({cp.first-y[i] + x[r[j]]-x[l[i]],2*j+1});
// }
// cp=upper_bound(r[i],y[i]);
// cout<<"At "<<i<<' '<<cp.first<<' '<<cp.second<<' '<<r[i]<<endl;;
// if (cp.first!=inf) {
// int j=cp.second;
// cout<<"j oth "<<j<<' '<<y[j]<<' '<<y[i]<<endl;
// cout<<"up cost "<<cp.first-y[i]<<endl;
// cout<<"right cost "<<x[r[j]]-x[r[i]]<<endl;
// ma[2*i+1].push_back({cp.first-y[i] + x[r[j]]-x[r[i]],2*j+1});
// // (w,n)
// }
// cp=lower_bound(l[i],y[i]);
// if (cp.first!=inf) {
// int j=cp.second;
// ma[2*i].push_back({y[i]-cp.first + x[r[j]]-x[l[i]],2*j+1});
// }
// cp=lower_bound(r[i],y[i]);
// if (cp.first!=inf) {
// int j=cp.second;
// ma[2*i+1].push_back({y[i]-cp.first + x[r[j]]-x[r[i]],2*j+1});
// // (w,n)
// }
// }
// for (int i=0;i<q;i++) {
// add(l[i],r[i],y[i],i+1);
// }
// for (int i=0;i<q;i++) {
// // node 2*i and 2*i-1
// ma[2*i].push_back({x[r[i]]-x[l[i]],2*i+1});
// auto cp=upper_bound(l[i],y[i]);
// if (cp.first!=inf) {
// int j=cp.second;
// ma[2*i].push_back({cp.first-y[i] + x[r[j]]-x[l[i]],2*j+1});
// }
// cp=upper_bound(r[i],y[i]);
// if (cp.first!=inf) {
// int j=cp.second;
// ma[2*i+1].push_back({cp.first-y[i] + x[r[j]]-x[r[i]],2*j+1});
// // (w,n)
// }
// cp=lower_bound(l[i],y[i]);
// if (cp.first!=inf) {
// int j=cp.second;
// ma[2*i].push_back({y[i]-cp.first + x[r[j]]-x[l[i]],2*j+1});
// }
// cp=lower_bound(r[i],y[i]);
// if (cp.first!=inf) {
// int j=cp.second;
// ma[2*i+1].push_back({y[i]-cp.first + x[r[j]]-x[r[i]],2*j+1});
// // (w,n)
// }
// }
for (int i=0;i<2*q;i++) {
dist[i]=inp;
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
for (int i=0;i<q;i++) {
if (l[i]==s) {
// start on base line
dist[2*i]=min(dist[2*i],(ll)y[i]);
pq.push({dist[2*i],2*i});
cout<<"Dist "<<dist[2*i]<<' '<<2*i<<' '<<y[i]<<endl;
}
if (r[i]==s) {
// start on base line
dist[2*i+1]=min(dist[2*i+1],(ll)y[i]);
pq.push({dist[2*i+1],2*i+1});
}
if(l[i]<=s and s<=r[i])
{
dist[2*i+1]=min(dist[2*i+1],(ll)(y[i]+x[r[i]]-x[s]));
pq.push({dist[2*i+1],2*i+1});
dist[2*i]=min(dist[2*i],(ll)(y[i]+x[s]-x[l[i]]));
pq.push({dist[2*i],2*i});
}
}
while (pq.size()) {
auto [d,u]=pq.top();pq.pop();
if (d>dist[u])continue;
// cout<<"PQ ";
// cout<<d<<' '<<u<<endl;
for (auto [w,v]:ma[u]) {
if (dist[v]>d+w) {
// cout<<"Edge "<<u<<' '<<v<<' '<<w<<endl;
dist[v]=d+w;
pq.push({dist[v],v});
}
}
}
ll ans=inp;
for (int i=0;i<q;i++) {
if (r[i]==g) {
ans=min(ans,dist[2*i+1]+y[i]);
}
if (l[i]==g) {
ans=min(ans,dist[2*i]+y[i]);
}
if(l[i]<=g and g<=r[i])
{
ans=min(ans,(ll)(y[i]+x[r[i]]-x[g])+dist[2*i+1]);
ans=min(ans,(ll)(y[i]+x[g]-x[l[i]])+dist[2*i]);
}
}
return ans;
}
// int main() {
// int n,m;
// cin>>n>>m;
// vector<int> x(n),h(n);
// for (int i=0;i<n;i++) {
// cin>>x[i]>>h[i];
// }
// vector<int> l(m),r(m),y(m);
// for (int i=0;i<m;i++) {
// cin>>l[i]>>r[i]>>y[i];
// }
// int s,g;
// cin>>s>>g;
// // while (m--) {
// cout<<min_distance(x,h,l,r,y,s,g)<<endl;
// // }
// }
