//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#include "rail.h"
#define MX_N 5001
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
//int getDistance(int i, int j){
// int res;
// cin >> res;
// return res;
//}
int d[MX_N][MX_N];
void findLocation(int n, int first, int location[], int stype[]){
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
d[i][j] = getDistance(i, j);
d[j][i] = d[i][j];
}
}
for(int i=0;i<n;++i){
location[i] = -1;
}
location[0] = first;
stype[0] = 1;
int shortest = 1000000009;
int B = -1;
for(int i=1;i<n;++i){
if(d[0][i] < shortest){
B = i;
shortest = d[0][i];
}
}
location[B] = first+d[B][0];
stype[B] = 2;
shortest = 1000000009;
int A = -1;
for(int i=0;i<n;++i){
if(i == B){
continue;
}
if(d[B][i] < shortest){
A = i;
shortest = d[B][i];
}
}
location[A] = location[B]-d[B][A];
stype[A] = 1;
vector<pair<int, int> > L, R;
for(int i=0;i<n;++i){
if(i == A || i == B){
continue;
}
if(d[A][i] < d[B][i]){
R.pb({d[A][i], i});
}else{
L.pb({d[B][i], i});
}
}
sort(All(L));
sort(All(R));
for(auto& [dist, i] : R){
if(location[i] != -1){
continue;
}
stype[i] = 2;
location[i] = location[A] + d[A][i];
for(int j=0;j<n;++j){
if(j == i){
continue;
}
if(location[j] != -1){
continue;
}
if(d[A][j] == d[A][i] + d[i][j]){
location[j] = location[i] - d[i][j];
stype[j] = 1;
}
}
}
for(auto& [dist, i] : L){
if(location[i] != -1){
continue;
}
stype[i] = 1;
location[i] = location[B] - d[B][i];
for(int j=0;j<n;++j){
if(j == i){
continue;
}
if(location[j] != -1){
continue;
}
if(d[B][j] == d[B][i] + d[i][j]){
location[j] = location[i] + d[i][j];
stype[j] = 2;
}
}
}
}
