#include "rail.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
const int maxn=5e3+5;
pair < int, int > dist[maxn];
vector < int > desne;
vector < int > pot;
void findLocation(int n, int pos, int sol1[], int sol2[]){
for(int i=1; i<n; i++){
dist[i-1]={getDistance(0, i), i};
}
sol1[0]=pos;
sol2[0]=1;
sort(dist, dist+n-1);
int l=0;
int d=dist[0].second;
int x;
sol1[d]=pos+dist[0].first;
sol2[d]=2;
desne.push_back(d);
int q1, q2;
bool p;
for(int i=1; i<n-1; i++){
x=dist[i].second;
q1=getDistance(l, x);
q2=getDistance(d, x);
for(int j=0; j<(int)desne.size(); j++){
pot.push_back(sol1[desne[j]]*2-q1-sol1[l]);
}
p=0;
for(int j=0; j<(int)desne.size(); j++){
if(sol1[d]-pot[j]==q2){
assert(!p);
assert(pot[j]>=0);
p=1;
sol1[x]=pot[j];
sol2[x]=1;
if(pot[j]<sol1[l]){
l=x;
}
}
}
pot.clear();
if(!p){
sol1[x]=sol1[l]+q1;
sol2[x]=2;
desne.push_back(x);
d=x;
}
}
}
