#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
int pos;
int ban[maxn];
int rec[maxn][maxn];
int ask(int x, int y) {
if(x>y) swap(x,y);
if(!rec[x][y]) rec[x][y] = getDistance(x,y);
// printf("\task %d %d = %d\n",x,y,rec[x][y]);
return rec[x][y];
}
void findLocation(int N, int first, int location[], int stype[]) {
//find right
ban[0] = 1;
while(1) {
int x = -1;
//nearest D
for(int i=0;i<N;i++) {
if(!ban[i] && (x==-1 || ask(0,i)<ask(0,x))) {
x = i;
}
}
if(x==-1) break;
pos = x;
ban[x] = 1;
//sweep left
for(int i=0;i<N;i++) {
if(!ban[i] && ask(0,i)-ask(0,x)==ask(x,i)) {
ban[i] = 1;
}
}
}
memset(ban,0,sizeof(ban));
ban[pos] = 1;
location[pos] = first + ask(0,pos);
stype[pos] = 2;
while(1) {
int x = -1;
//nearest C
for(int i=0;i<N;i++) {
if(!ban[i] && (x==-1 || ask(pos,i)<ask(pos,x))) {
x = i;
}
}
if(x==-1) break;
ban[x] = 1;
location[x] = location[pos] - ask(pos,x);
stype[x] = 1;
// printf("%d (%d): ",x,location[x]);
//sweep right
for(int i=0;i<N;i++) {
if(!ban[i] && ask(pos,i)-ask(pos,x)==ask(x,i)) {
ban[i] = 1;
location[i] = location[x] + ask(x,i);
stype[i] = 2;
// printf("%d (%d) ",i,location[i]);
}
}
// printf("\n");
}
// for(int i=0;i<N;i++) printf("%d %d\n",stype[i],location[i]);
}
