#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
int n,all[maxn][maxn];
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
location[0]=first;
stype[0]=1;
if(n==1){
return ;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
all[i][j]=all[j][i]=getDistance(i,j);
}
}
int res1=0,res2=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int z=0;
for(int h=0;h<n;h++){
if(h==i||h==j){
continue;
}
if(all[i][j]==all[i][h]+all[h][j]){
z=1;
}
}
if(z==0){
res1=i;
res2=j;
}
}
}
int mn=1e7,wh=-1;
for(int i=1;i<n;i++){
if(mn>all[0][i]){
wh=i;
mn=all[0][i];
}
}
if(all[res1][wh]+all[res2][wh]!=all[res1][res2]+all[0][wh]){
swap(res1,res2);
}
stype[res1]=1;
stype[res2]=2;
//cout<<res1<<" wef "<<res2<<endl;
location[res2]=first+all[0][res2];
location[res1]=location[res2]-all[res2][res1];
for(int i=0;i<n;i++){
if(i==res1||i==res2||i==0){
continue;
}
if(all[res2][0]+all[0][i]==all[res2][i]){
stype[i]=2;
location[i]=first+all[0][i];
}else{
stype[i]=1;
location[i]=location[res2]-all[res2][i];
}
}
}
