#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 2;
int dist[N][N], used[N];
void findLocation(int N, int first, int location[], int stype[]){
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 ++){
dist[i][j] = dist[j][i] = getDistance(i, j);
}
}
vector <int> rd, lc;
int a = 1, b = 0;
for(int i = 2; i < N; i ++){
if(dist[0][i] < dist[0][a])
a = i;
}
rd.push_back(a);
for(int i = 1; i < N; i ++){
if(i == a) continue;
if(dist[a][i] < dist[a][b])
b = i;
}
if(b){
used[b] = 1;
stype[b] = 1;
location[b] = (location[0] + dist[0][a]) - dist[a][b];
}
for(int i = 1; i < N; i ++){
if(i == a || i == b) continue;
int x = dist[0][i], c = dist[a][i], d = dist[a][b], mn = dist[0][a];
if(x - mn == c - d * 2)
rd.push_back(i);
if(x - mn == c)
lc.push_back(i);
}
for(int i : rd){
location[i] = dist[0][i] + first;
stype[i] = 2;
used[i] = 1;
}
for(int i : lc){
location[i] = location[a] - dist[a][i];
stype[i] = 1;
used[i] = 1;
}
for(int i = 1; i < N; i ++){
if(!used[i]){
for(int j : rd){
int x = dist[0][j], y = dist[j][i], z = dist[0][i];
if(z - y == x){
stype[i] = 1;
location[i] = location[j] - y;
used[i] = 1;
}
}
}
}
for(int i = 1; i < N; i ++){
if(!used[i]){
int id = 0;
for(int j = 0; j < N; j ++){
if(j == i) continue;
if(dist[i][j] < dist[i][id])
id = j;
}
stype[i] = 2;
location[i] = location[id] + dist[i][id];
}
}
}
