#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define oo 1000000000
void findLocation(int n, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
vector<vector<int>> dist(n, vector<int>(n));
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<set<pair<int, int>>> st(n);
for (int i = 0; i < n; ++i){
for (int j = 1; j < n; ++j) st[i].insert({dist[i][j], j});
}
vector<bool> found(n); found[0] = true;
for (int i = 0; i < n-1; ++i){
int mni = -1, mn = oo;
for (int j = 0; j < n; ++j){
if (!found[j]) continue;
if (mni == -1 || st[j].begin()->first < mn) mni = j, mn = st[j].begin()->first;
}
assert(mni != -1);
int to = st[mni].begin()->second;
if (stype[mni] == 1){
location[to] = location[mni] + mn;
stype[to] = 2;
} else{
location[to] = location[mni] - mn;
stype[to] = 1;
}
found[to] = true;
for (int j = 0; j < n; ++j){
st[j].erase({dist[j][to], to});
}
}
}
