#include "rail.h"
#include<algorithm>
using namespace std;
typedef pair<int,int> Pi;
#define X first
#define Y second
int F[5050], T[5050];
Pi tF[5050], tT[5050];
int tf, tt;
int st[5050], top;
int val[5050];
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first, stype[0] = 1;
int i, tar = 1;
for(i=1;i<N;i++){
F[i] = getDistance(0, i);
if(F[tar] > F[i])tar = i;
}
location[tar] = F[tar] + first;
stype[tar] = 2;
for(i=1;i<N;i++)if(i != tar)T[i] = getDistance(tar, i);
for(i=1;i<N;i++){
if(i == tar)continue;
if(F[i] == T[i] + F[tar])tT[tt++] = Pi(T[i], i);
else tF[tf++] = Pi(F[i] - F[tar], i);
}
sort(tT, tT+tt);
sort(tF, tF+tf);
if(tt)val[tT[0].Y] = tT[0].X, stype[tT[0].Y] = 1;
st[top++] = tT[0].Y;
for(i=1;i<tt;i++){
int t = getDistance(tT[i].Y, st[top-1]), j;
for(j=0;j<top;j++){
int b = val[st[j]]*2 - tT[i].X;
if(val[st[top-1]]-b == t)break;
}
if(j == top){
val[tT[i].Y] = tT[i].X, stype[tT[i].Y] = 1;
st[top++] = tT[i].Y;
}
else{
val[tT[i].Y] = val[st[j]]*2 - tT[i].X, stype[tT[i].Y] = 2;
}
}
for(i=0;i<tt;i++)location[tT[i].Y] = location[tar] - val[tT[i].Y];
top = 0;
if(tf)val[tF[0].Y] = tF[0].X, stype[tF[0].Y] = 2;
st[top++] = tF[0].Y;
for(i=1;i<tf;i++){
int t = getDistance(tF[i].Y, st[top-1]), j;
for(j=0;j<top;j++){
int b = val[st[j]]*2 - tF[i].X;
if(val[st[top-1]]-b == t)break;
}
if(j == top){
val[tF[i].Y] = tF[i].X, stype[tF[i].Y] = 2;
st[top++] = tF[i].Y;
}
else{
val[tF[i].Y] = val[st[j]]*2 - tF[i].X, stype[tF[i].Y] = 1;
}
}
for(i=0;i<tf;i++)location[tF[i].Y] = location[tar] + val[tF[i].Y];
}
