#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 5005;
ll dist[N][N];
ll D(ll i, ll j){
if(i == j) return 0;
if(dist[i][j] != -1) return dist[i][j];
dist[i][j] = dist[j][i] = getDistance(i, j);
return dist[i][j];
}
void findLocation(int n, int first, int location[], int stype[]){
memset(dist, -1, sizeof(dist));
ii mn = {1e9, 0};
location[0] = first; stype[0] = 1;
if(n == 1) return;
for(ll i = 1; i < n; i++){
mn = min(mn, {D(0, i), i});
}
ll D_block = mn.ss; ll C_block = 0;
location[D_block] = first + mn.ff;
stype[D_block] = 2;
vector < ll > before, middle, after;
for(ll i = 0; i < n; i++){
if(i == D_block || i == C_block) continue;
ll y = D(D_block, i);
ll x = D(C_block, i);
ll z = D(C_block, D_block);
if(x - y == z && y > z) before.pb(i);
else{
if(y < z && x == y + z){
middle.pb(i);
stype[i] = 1;
location[i] = location[D_block] - y;
}else after.pb(i);
}
}
sort(before.begin(), before.end(), [&](ll i, ll j){
return D(D_block, i) < D(D_block, j);
});
sort(after.begin(), after.end(), [&](ll i, ll j){
return D(C_block, i) < D(C_block, j);
});
ll last = -1;
//cout << before.size() << ' ' << middle.size() << ' ' << after.size() << '\n';
for(auto i : after){
if(last == -1){
location[i] = location[C_block] + D(C_block, i);
stype[i] = 2;
last = i;
continue;
}
ll x = D(C_block, i);
ll y = D(last, i);
ll z = D(last, C_block);
if(y < z && x == y + z){
location[i] = location[last] - y;
stype[i] = 1;
}else{
location[i] = location[C_block] + x;
stype[i] = 2;
last = i;
}
}
last = -1;
for(auto i : before){
if(last == -1){
location[i] = location[D_block] - D(D_block, i);
stype[i] = 1;
last = i;
continue;
}
ll x = D(D_block, i);
ll y = D(last, i);
ll z = D(last, D_block);
if(y < z && x == y + z){
location[i] = location[last] + y;
stype[i] = 2;
}else{
location[i] = location[D_block] - x;
stype[i] = 1;
last = i;
}
}
return;
}
