#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N=5010, M=1e6+10;
int n;
int mem[N][N], tt[M];
int dist(int i, int j){
if (i==j) return 0;
if (mem[i][j]!=-1) return mem[i][j];
return mem[i][j]=mem[j][i]=getDistance(i, j);
}
void findLocation(int N_, int first, int pos[], int t[])
{
memset(mem, -1, sizeof mem);
n=N_;
pos[0]=first;
t[0]=1; tt[pos[0]]=1;
int ir=1;
for (int i=1; i<n; ++i) if (dist(0, i)<dist(0, ir)) ir=i;
pos[ir]=pos[0]+dist(0, ir); t[ir]=2; tt[pos[ir]]=2;
int il=0;
vector<int> vl, vr;
for (int i=0; i<n; ++i) if (i!=ir && i!=il){
if (dist(i, il)==dist(i, ir)+dist(il, ir)){
if (dist(i, ir)<dist(il, ir)){
pos[i]=pos[ir]-dist(i, ir);
t[i]=1; tt[pos[i]]=1;
}else vl.push_back(i);
}else{
vr.push_back(i);
}
}
sort(vl.begin(), vl.end(), [&](int x, int y){ return dist(il, x)<dist(il, y); });
sort(vr.begin(), vr.end(), [&](int x, int y){ return dist(il, x)<dist(il, y); });
int ll=il, rr=ir;
for (int i:vr){
int p=(dist(ll, i)-dist(rr, i)+pos[ll]+pos[rr])/2;
if (tt[p]==2){
pos[i]=pos[rr]-dist(rr, i);
t[i]=1; tt[pos[i]]=1;
}else{
pos[i]=pos[ll]+dist(ll, i);
t[i]=2; tt[pos[i]]=2;
rr=i;
}
}
ll=il, rr=ir;
for (int i:vl){
int p=(dist(ll, i)-dist(rr, i)+pos[ll]+pos[rr])/2;
if (tt[p]==1){
pos[i]=pos[ll]+dist(ll, i);
t[i]=2; tt[pos[i]]=2;
}else{
pos[i]=pos[rr]-dist(rr, i);
t[i]=1; tt[pos[i]]=1;
ll=i;
}
}
for (int i:vl) assert(pos[i]<pos[ir]);
for (int i:vr) assert(pos[i]>pos[il]);
}
