#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
const int N = 5e3 + 100;
const int INTmx = (int)1e9;
int a[N],b[N],n;
bool ban[N];
int sd[N];
bool was[N][N];
int c[N][N];
int get(int x,int y) {
if(was[x][y])return c[x][y];
was[x][y] = 1;
c[x][y] = getDistance(x,y);
return c[x][y];
}
void findLocation(int NN, int first, int location[], int stype[]) {
n = NN;
location[0] = first;
stype[0] = 1;
pii mn = mp(INTmx,0);
int L = 0;
ban[0] = 1;
for(int i = 1;i < n;i++) {
if(ban[i])continue;
mn = min(mn,mp(get(L,i),i));
}
int R = mn.s;
ban[R] = 1;
location[R] = location[L] + get(L,R);
stype[R] = 2;
int kol = 2;
for(int i = 1;i < n;i++) {
if(ban[i])continue;
if(get(L,i) == get(R,i) + get(L,R) && get(R,i) < get(L,R)) {
stype[i] = 1;
location[i] = location[R] - get(R,i);
ban[i] = 1;
kol++;
}
}
//cout << R << " " << stype[R] << endl;
while(kol < n) {
mn = mp(INTmx,0);
pii mn1 = mp(INTmx,0);
for(int i = 1;i < n;i++) {
if(ban[i])continue;
mn = min(mn,mp(get(L,i),i));
mn1 = min(mn1,mp(get(R,i),i));
}
if(get(R,mn.s) == get(L,mn.s) + get(L,R)) {
kol++;
R = mn.s;
ban[R] = 1;
//cout << "change R to " << R << endl;
location[R] = location[L] + get(L,R);
stype[R] = 2;
for(int i = 1;i < n;i++) {
if(ban[i])continue;
if(get(L,i) == get(R,i) + get(L,R) && get(R,i) < get(L,R)) {
stype[i] = 1;
location[i] = location[R] - get(R,i);
ban[i] = 1;
kol++;
}
}
}else {
kol++;
L = mn1.s;
ban[L] = 1;
//cout << "change L to " << L << endl;
location[L] = location[R] - get(R,L);
stype[L] = 1;
for(int i = 1;i < n;i++) {
if(ban[i])continue;
if(get(R,i) == get(L,i) + get(R,L) && get(L,i) < get(R,L)) {
stype[i] = 2;
location[i] = location[L] + get(L,i);
ban[i] = 1;
kol++;
}
}
}
//cout << L << " " << R << endl;
}
}
