#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using pp=pair<int,int>;
#define x first
#define y second
pp kyori[5010];
int dc[5010][5010];
int dst(int a, int b){
if(dc[a][b]) return dc[a][b];
return dc[a][b]=dc[b][a]=getDistance(a, b);
}
void findLocation(int n, int first, int location[], int stype[])
{
for(int i=1; i<n; ++i) kyori[i-1]={dst(0, i), i};
sort(kyori, kyori+n-1);
int L = 0, Lp = first, R = kyori[0].y, Rp = Lp + kyori[0].x;
location[L] = Lp;
location[R] = Rp;
stype[L] = 1; stype[R] = 2;
for(int i=1; i<n-1; ++i){
int j = kyori[i].y;
int dl = dst(L, j), dr = dst(R, j);
int jp;
if(dl < dr){
jp = Lp + dl;
stype[j] = 2;
if(jp > Rp){
R = j;
Rp = jp;
}
} else {
jp = Rp - dr;
stype[j] = 1;
if(jp < Lp){
L = j;
Lp = jp;
}
}
location[j] = jp;
}
}
