#include "rail.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
map<pair<int,int>,int> m;
int get(int a,int b){
if(a>b){
swap(a,b);
}
if(a==b){
return 0;
}
if(m.find(pair<int,int>(a,b))==m.end()){
m[pair<int,int>(a,b)]=getDistance(a,b);
}
return m[{a,b}];
}
void findLocation(int n, int fr, int l[], int s[]){
vector<int> d0(n),d1(n);
int mn=-1;
for(int i=1;i<n;i++){
d0[i]=get(0,i);
if(mn==-1 || d0[i]<d0[mn]){
mn=i;
}
}
l[0]=fr;
s[0]=1;
l[mn]=fr+d0[mn];
s[mn]=2;
vector<int> d;
vector<pair<int,int> > a,b;
for(int i=0;i<n;i++){
d1[i]=get(mn,i);
if(i==mn || i==0){
continue;
}
if(d0[i]==d1[i]+d0[mn]){
if(d1[i]<d0[mn]){
l[i]=l[mn]-d1[i];
s[i]=1;
d.push_back(-l[i]);
}
else{
a.push_back({d1[i],i});
}
}
else{
b.push_back({d0[i],i});
}
}
//b -> right, a -> left
d.push_back(-l[0]);
sort(a.begin(),a.end());
{
int u=0;
for(auto h:a){
int x=get(u,h.sc);
int f=l[u]+x;
int y=-(*lower_bound(d.begin(),d.end(),-f));
if(y==f || h.fs!=f+l[mn]-2*y){
l[h.sc]=l[mn]-d1[h.sc];
s[h.sc]=1;
d.push_back(-l[h.sc]);
u=h.sc;
}
else{
s[h.sc]=2;
l[h.sc]=f;
}
}
}
sort(b.begin(),b.end());
{
int u=mn;
vector<int> c;
c.push_back(l[mn]);
for(auto h:b){
int x=get(u,h.sc);
int f=l[u]-x;
int y=*lower_bound(c.begin(),c.end(),f);
if(y==f || h.fs!=2*y-l[0]-f){
l[h.sc]=l[0]+d0[h.sc];
s[h.sc]=2;
c.push_back(l[h.sc]);
u=h.sc;
}
else{
s[h.sc]=1;
l[h.sc]=f;
}
}
}
}
