#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll dist[5005][5005];
ll loc[1000005];
ll getdist(ll i, ll j){
if(i==j)return 0;
if(dist[i][j])return dist[i][j];
dist[i][j]=dist[j][i]=getDistance(i,j);
return dist[i][j];
}
void findLocation(int n, int first, int location[],int stype[]){
location[0]=first,stype[0]=1;
loc[first]=0;
if(n==1)return;
int st=0;
vector<pair<ll,ll> >from,hi,mi;
for(int i=1;i<n;i++){
from.pb({getdist(st,i),i});
}
sort(from.begin(),from.end());
ll req=from[0].second;
location[req]=location[0]+getdist(0,req);stype[req]=2;
for(int i=0;i<n;i++){
if(i==st||i==req)continue;
if(getdist(st,i)==getdist(req,i)+getdist(st,req)&&getdist(req,i)<getdist(st,req)){
stype[i]=1;location[i]=location[req]-getdist(req,i);continue;
}
if(getdist(st,i)==getdist(req,i)+getdist(st,req)){
hi.push_back({getdist(st,i),i});
}
else{
mi.push_back({getdist(req,i),i});
}
}
sort(hi.begin(),hi.end());
sort(mi.begin(),mi.end());
ll init,init2;
for(int i=0;i<hi.size();i++){
if(i==0){
ll nd=hi[i].second;
stype[nd]=1,location[nd]=location[req]-getdist(req,nd);
init=nd;continue;
}
ll nd=hi[i].second;
ll v=getdist(init,nd)+getdist(req,nd)-getdist(init,req);v/=2;
if(location[init]+getdist(init,nd)-v!=location[init]){
location[nd]=location[req]-getdist(req,nd);
stype[nd]=1;init=nd;
}
else{
location[nd]=location[init]+v;
stype[nd]=2;
}
}
for(int i=0;i<mi.size();i++){
if(i==0){
ll nd=mi[i].second;
stype[nd]=2,location[nd]=location[st]+getdist(st,nd);
init=nd;continue;
}
ll nd=mi[i].second;
ll v=getdist(init,nd)+getdist(st,nd)-getdist(init,st);v/=2;
if(location[init]-getdist(init,nd)+v!=location[init]){
location[nd]=location[st]+getdist(st,nd);
stype[nd]=2;init=nd;
}
else{
location[nd]=location[init]-v;
stype[nd]=1;
}
}
}
