#include "rail.h"
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
using namespace std;
ll dis[5005][5005], opt[5005];
void findLocation(int n, int first, int location[], int stype[])
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(i<j) dis[i][j]=getDistance(i, j);
else dis[i][j]=dis[j][i];
}
}
vector<pii>d0;
for(int i=1; i<n; i++)
{
d0.pb({dis[0][i], i});
}
sort(all(d0));
int l=0, r=d0[0].S;
stype[0]=1;
location[0]=first;
stype[d0[0].S]=2;
location[d0[0].S]=first+d0[0].F;
for(int i=1; i<n-1; i++)
{
int k=d0[i].S;
bool f=0;
if(dis[l][k]>dis[r][k]) f=1;
for(int e=0; e<n; e++)
{
if(e!=l and e!=k and dis[l][e]+dis[e][k]==dis[l][k])
{
f=1;
break;
}
}
for(int e=0; e<n; e++)
{
if(e!=r and e!=k and dis[r][e]+dis[e][k]==dis[r][k])
{
f=0;
break;
}
}
if(f)
{
stype[k]=1;
location[k]=location[r]-dis[r][k];
if(location[k]<location[l]) l=k;
}
else
{
stype[k]=2;
location[k]=location[l]+dis[l][k];
if(location[k]>location[r]) r=k;
}
}
}
