#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;
int dis[5005][5005], t[1000005];
int gdis(int i, int j)
{
if(dis[i][j]==-1) dis[i][j]=dis[j][i]=getDistance(i, j);
return dis[i][j];
}
void findLocation(int n, int first, int location[], int stype[])
{
memset(dis, -1, sizeof(dis));
vector<pii>d0;
for(int i=1; i<n; i++)
{
d0.pb({gdis(0, i), i});
}
sort(all(d0));
int l=0, r=d0[0].S;
t[location[0]]=stype[0]=1;
location[0]=first;
t[location[d0[0].S]]=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(gdis(l, k)>gdis(r, k)) f=1;
int e=((l+gdis(l,k))+(r-gdis(r,k)))>>1;
if(t[e]==2) f=1;
else if(t[e]==1) f=0;
if(f)
{
stype[k]=1;
location[k]=location[r]-gdis(r, k);
t[location[k]]=1;
if(location[k]<location[l]) l=k;
}
else
{
stype[k]=2;
location[k]=location[l]+gdis(l, k);
t[location[k]]=2;
if(location[k]>location[r]) r=k;
}
}
}
