//In the name of God
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 5100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll dis[maxn][maxn];
bool isr[maxn];
void findLocation(int n, int first, int loc[], int st[]){
for(ll i = 0; i < n; i++){
for(ll j = i + 1; j < n; j++){
dis[i][j] = dis[j][i] = getDistance(i, j);
}
}
ll x = 1;
for(ll i = 1; i < n; i++){
if(dis[0][i] < dis[0][x]) x = i;
}
st[0] = 1;
for(ll i = 1; i < n; i++){
if(dis[0][x] > dis[x][i] || x == i || dis[0][i] != dis[0][x] + dis[x][i]) isr[i] = 1;
}
while(true){
ll y = -1;
for(ll i = 1; i < n; i++){
if(st[i]) continue;
if(!isr[i]) continue;
if(y == -1 || dis[0][y] > dis[0][i]) y = i;
}
if(y == -1) break;
st[y] = 2;
loc[y] = dis[0][y];
ll z = 0;
for(ll i = 0; i < n; i++){
if(i == y) continue;
if(dis[y][i] < dis[y][z]) z = i;
}
if(st[z]) continue;
loc[z] = 2 * dis[0][y] - dis[0][z];
st[z] = 1;
for(ll i = 0; i < n; i++){
if(st[i]) continue;
if(!isr[i]) continue;
if(dis[y][i] < dis[z][i]){
st[i] = 1;
loc[i] = 2 * dis[0][y] - dis[0][i];
}
}
}
while(true){
ll y = -1;
for(ll i = 1; i < n; i++){
if(isr[i] || st[i]) continue;
if(y == -1 || dis[x][y] > dis[x][i]) y = i;
}
if(y == -1) break;
st[y] = 1;
loc[y] = dis[0][x] - dis[x][y];
ll z = 0;
for(ll i = 0; i < n; i++){
if(i == y) continue;
if(dis[y][i] < dis[y][z]) z = i;
}
if(st[z]) continue;
loc[z] = dis[0][x] - (2 * dis[x][y] - dis[x][z]);
st[z] = 2;
for(ll i = 0; i < n; i++){
if(isr[i] || st[i]) continue;
if(dis[y][i] < dis[z][i]){
st[i] = 2;
loc[i] = dis[0][x] - (2 * dis[x][y] - dis[x][i]);
}
}
}
loc[0] = 0;
for(ll i = 0; i < n; i++){
loc[i] += first;
}
return;
}
/*int main(){
fast_io;
return 0;
}*/
