#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
int d0[maxn], d1[maxn];
void findLocation(int N, int first, int location[], int stype[]) {
int x = 1;
for(int i=1;i<N;i++) {
d0[i] = getDistance(0,i);
if(d0[i]<d0[x]) x = i;
}
for(int i=1;i<N;i++) if(i!=x) d1[i] = getDistance(x,i);
location[0] = first; stype[0] = 1;
location[x] = first+d0[x]; stype[x] = 2;
for(int i=1;i<N;i++) {
if(i==x) continue;
if(d0[i]==d1[i]+d0[x]) location[i] = location[x]-d1[i], stype[i] = 1;
else location[i] = location[0]+d0[i], stype[i] = 2;
}
}
