#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
const int maxn = 5e3;
const int inf = 1e9;
int memo[maxn][maxn];
int get(int i, int j){
if(i == j) return 0;
if(memo[i][j] != -1){
return memo[i][j];
}
return memo[i][j] = memo[j][i] = getDistance(i, j);
}
void findLocation(int n, int first, int location[], int stype[])
{
for(int i = 0; i < n; i ++){
location[i] = -1;
for(int j = 0; j < n; j ++){
memo[i][j] = -1;
}
}
location[0] = first;
stype[0] = 1;
if(n == 1){
return;
}
int rig = 0, mn = inf + 1;
for(int i = 1; i < n; i ++){
if(get(0, i) < mn){
mn = get(0, i);
rig = i;
}
}
int lef = 0;
mn = get(0, rig);
location[rig] = first + get(0, rig);
stype[rig] = 2;
for(int i = 1; i < n; i ++){
if(location[i] != -1) continue;
if(mn > get(rig, i)){
mn = get(rig, i);
lef = i;
}
}
location[lef] = location[rig] - get(rig, lef);
stype[lef] = 1;
vector<pair<int,int>> lefs, rigs;
for(int i = 0; i < n; i ++){
if(location[i] != -1) continue;
if(get(0, i) == get(0, rig) + get(rig, i)){
lefs.push_back({get(0, i), i});
}else{
rigs.push_back({get(0, i), i});
}
}
sort(all(rigs));
sort(all(lefs));
for(auto [d, i] : rigs){
memo[lef][i] = memo[i][lef] = get(rig, i) - get(lef, rig);
}
int last = rig;
for(auto [d, i] : rigs){
if(get(lef, i) == get(last, i) + get(lef, last)){
location[i] = location[last] - get(last, i);
stype[i] = 1;
}else{
location[i] = location[lef] + get(lef, i);
stype[i] = 2;
last = i;
}
}
last = lef;
for(auto [d, i] : lefs){
if(get(rig, i) == get(last, i) + get(rig, last)){
location[i] = location[last] + get(last, i);
stype[i] = 2;
}else{
location[i] = location[rig] - get(rig, i);
stype[i] = 1;
last = i;
}
}
}
