#include "rail.h"
#include<iostream>
#include<set>
#include<vector>
using namespace std;
const int N = 5055;
const int inf = 1e9;
int da[N], db[N];
int a = -1, b = -1;
int ask(int x, int y) {
if (x == y) return 0;
if (x == a) return da[y];
if (x == b) return db[y];
return getDistance(x, y);
}
int n;
void findLocation(int N, int first, int location[], int stype[]) {
n = N;
a = 0;
stype[0] = 1, location[0] = first;
for (int i = 0 ; i < n ; ++ i) {
if (i == a) continue;
da[i] = getDistance(a, i);
}
int mn = inf;
for (int i = 0 ; i < n ; ++ i) {
if (i == a) continue;
if (mn > da[i]) {
mn = da[i];
b = i;
}
}
for (int i = 0 ; i < n ; ++ i) {
if (i == a || i == b) continue;
db[i] = getDistance(b, i);
}
stype[b] = 2, location[b] = location[a] + da[b];
vector<int>left, right;
for (int i = 0 ; i < n ; ++ i) {
if (i == a || i == b) {
continue;
}
if (da[i] < db[i]) {
right.emplace_back(i);
} else {
left.emplace_back(i);
}
}
for (int i : left) {
location[i] = location[b] - db[i];
if (getDistance(i, b) == db[i]) {
stype[i] = 1;
} else {
stype[i] = 2;
}
}
for (int i : right) {
location[i] = location[a] + da[i];
if (getDistance(i, a) == da[i]) {
stype[i] = 2;
} else {
stype[i] = 1;
}
}
}
