#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define MAX 5005
#define ii pair<int,int>
#define st first
#define nd second
#define pb push_back
#define inf 1000000001
int dist[MAX][MAX];
void findLocation(int N, int first, int location[], int stype[]) {
int Min=inf;
int tut=0;
for(int i=0;i<N;i++) {
for(int j=0;j<i;j++) {
dist[i][j]=dist[j][i]=getDistance(i,j);
}
if(i>0) {
if(Min>dist[i][0]) {
Min=dist[i][0];
tut=i;
}
}
}
location[tut]=first+dist[tut][0];
location[0]=first;
stype[0]=1;
stype[tut]=2;
for(int i=0;i<N;i++) {
if(i==tut || i==0) continue ;
if(dist[i][tut]<dist[i][0]) {
stype[i]=1;
location[i]=location[tut]-dist[i][tut];
}
else {
stype[i]=2;
location[i]=location[0]+dist[i][0];
}
}
}
