#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5003;
int dist0[N], p[N], dist[N][N];
bool xet[N];
void findLocation(int n, int pos0, int a[], int t[]) {
memset(dist, -1, sizeof dist);
auto get = [&] (int l, int r) -> int {
assert(l != r && l >= 0 && l < n && r >= 0 && r < n);
if (dist[l][r] != -1) return dist[l][r];
return dist[l][r] = dist[r][l] = getDistance(l, r);
};
auto apply = [&] (int i, int pos, int type) -> void {
a[i] = pos;
t[i] = type;
};
apply(0, pos0, 1);
if (n == 1) return;
for (int i = 1; i < n; i++) dist0[i] = getDistance(0, i);
iota(p, p + n, 0);
sort(p + 1, p + n, [] (int x, int y) {
return dist0[x] < dist0[y];
});
int r = p[1], l = 0;
apply(r, pos0 + dist0[r], 2);
for (int i = 2; i < n; i++) {
int x = p[i], to_l = get(l, x), to_r = get(r, x);
bool isApplied = false;
for (int j = 0; j < i; j++) {
if (t[j] == 1 && a[r] - a[j] + (a[l] + to_l) - a[j] == to_r) {
apply(x, a[l] + to_l, 2);
isApplied = true;
break;
}
}
if (!isApplied && get(p[1], x) + a[p[1]] - a[0] == dist0[x]) {
apply(x, a[p[1]] - get(p[1], x), 1);
isApplied = true;
}
if (!isApplied) apply(x, pos0 + dist0[x], 2);
if (t[x] == 1 && a[x] < a[l]) l = x;
if (t[x] == 2 && a[x] > a[r]) r = x;
}
}
