#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
long long int typedef li;
int dist[5003][5003];
int d(int i, int j)
{
if (i>j) swap(i,j);
if (!dist[i][j]) dist[i][j]=getDistance(i,j);
return dist[i][j];
}
void findLocation(int n, int first, int location[], int stype[])
{
location[0]=first,stype[0]=1;
int koji=-1,sta=1e9;
for (int i=1;i<n;i++) if (d(0,i)<sta) koji=i,sta=d(0,i);
location[koji]=first+d(0,koji),stype[koji]=2;
int second=location[koji];
for (int i=1;i<n;i++) if (i!=koji)
{
int a=d(0,i);
int b=d(koji,i);
if (a<b)
{
stype[i]=2;
location[i]=a+first;
}
else
{
stype[i]=1;
location[i]=second-b;
}
}
}
