#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int MAXN = 5010;
const int MOD = 1e9 + 7;
int n , mark[MAXN] , mn[MAXN];
void findLocation(int N, int first, int location[], int stype[]){
n = N;
fill(mn , mn + MAXN , MOD);
mn[0] = 0 ; location[0] = first; stype[0] = 1;
for(int i = 0 ; i < n ; i++){
int v = -1;
for(int j = 0 ; j < n ; j++){
if(!mark[j] && (v == -1 || mn[j] < mn[v])) v = j;
}
mark[v] = 1;
for(int j = 0 ; j < n ; j++){
if(mark[j]) continue;
int dist = getDistance(v , j);
if(dist < mn[j]){
mn[j] = dist;
location[j] = location[v] + dist * (stype[v] == 1 ? 1 : -1);
stype[j] = 3 - stype[v];
}
}
}
}
