#include "rail.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define pb push_back
const int N=5050;
int dist[N][N];
int Get(int i, int j)
{
if(i>j) return Get(j,i);
if(dist[i][j]) return dist[i][j];
return dist[i][j]=getDistance(i,j);
}
map<int,int> dir;
int fir=1;
bool comp1(int i, int j){ return Get(0,i)<Get(0,j);}
bool comp2(int i, int j){ return Get(fir,i)<Get(fir,j);}
void findLocation(int n, int st, int d[], int t[])
{
d[0]=st;
t[0]=1;
dir[d[0]]=t[0];
if(n==1) return;
int i,j;fir=1;
vector<int> left,right;
for(i=2;i<n;i++) if(Get(0,fir)>Get(0,i)) fir=i;
d[fir]=st+Get(0,fir);
t[fir]=2;
dir[d[fir]]=t[fir];
for(i=1;i<n;i++)
{
if(i==fir) continue;
if(Get(0,i)==d[fir]-d[0]+Get(fir,i))
{
if(d[fir]-d[0]>Get(fir,i))
{
t[i]=1;
d[i]=d[fir]-Get(fir,i);
dir[d[i]]=t[i];
}
else left.pb(i);
}
else right.pb(i);
}
sort(left.begin(),left.end(),comp2);
sort(right.begin(),right.end(),comp1);
int l=0,r=fir;
for(i=0;i<left.size();i++)
{
int x=left[i];
int val=(d[r]-d[l]+Get(l,x)-Get(r,x))/2;
if(dir[d[l]+val]==1)
{
d[x]=d[l]+Get(l,x);
t[x]=2;
dir[d[x]]=t[x];
}
else
{
d[x]=d[r]-Get(r,x);
t[x]=1;
dir[d[x]]=t[x];
l=x;
}
}
l=0;r=fir;
for(i=0;i<right.size();i++)
{
int x=right[i];
int val=(d[r]-d[l]+Get(r,x)-Get(l,x))/2;
if(dir[d[r]-val]==2)
{
d[x]=d[r]-Get(r,x);
t[x]=1;
dir[d[x]]=t[x];
}
else
{
d[x]=d[l]+Get(l,x);
t[x]=2;
dir[d[x]]=t[x];
r=x;
}
}
}
