#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
int dis[5005][5005],minind[5005];
void findLocation(int n, int first, int location[], int stype[])
{
location[0]=first;
stype[0]=1;
if(n==1)return ;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
dis[i][j]=getDistance(i,j);
dis[j][i]=dis[i][j];
}
}
for(int i=0;i<n;i++)
{
minind[i]=i;
for(int j=0;j<n;j++)
{
if(i==j)continue;
if(minind[i]==i || dis[i][minind[i]]>dis[i][j])minind[i]=j;
}
}
int c0,d0;
d0=minind[0];
location[d0]=location[0]+dis[0][d0];
stype[d0]=2;
c0=minind[d0];
location[c0]=location[d0]-dis[d0][c0];
stype[c0]=1;
for(int i=0;i<n;i++)
{
if(i==c0 || i==d0)continue;
if(dis[c0][i] < dis[d0][i]) // right
{
if(minind[i]==c0 || dis[c0][minind[i]]>dis[c0][minind[minind[i]]]) // d type
{
location[i]=location[c0]+dis[c0][i];
stype[i]=2;
}
else
{
location[i]=location[c0]+dis[c0][minind[i]]-dis[i][minind[i]];
stype[i]=1;
}
}
else //left
{
if(minind[i]==d0 || dis[d0][minind[i]]>dis[d0][minind[minind[i]]]) // c type
{
location[i]=location[d0]-dis[d0][i];
stype[i]=1;
}
else
{
location[i]=location[d0]-dis[d0][minind[i]]+dis[i][minind[i]];
stype[i]=2;
}
}
}
//for(int i=0;i<n;i++)printf("%d %d\n",location[i],stype[i]);
return ;
}
