#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e3 + 20;
const int maxM = 1e6 + 20;
int *location;
int *stype;
int btype[maxM];
int memo[maxN][maxN];
int X, Y, L, R;
int dist(int u, int v) {
if (memo[u][v] != -1) {
return memo[u][v];
}
else {
return memo[u][v] = memo[v][u] = getDistance(u, v);
}
}
bool cmpX(int u, int v) {
return dist(X, u) < dist(X, v);
}
bool cmpY(int u, int v) {
return dist(Y, u) < dist(Y, v);
}
void answer(int id, int loc, int type) {
location[id] = loc;
stype[id] = type;
btype[loc] = type;
}
void findLocation(int N, int first, int _location[], int _stype[]) {
location = _location;
stype = _stype;
for (int i = 0; i < N; i++) {
location[i] = -1;
stype[i] = -1;
for (int j = 0; j < N; j++) {
memo[i][j] = -1;
}
}
for (int i = 0; i < maxM; i++) {
btype[i] = -1;
}
X = 0;
answer(X, first, 1);
Y = 1;
for (int i = 0; i < N; i++) {
if (i != X && dist(X, i) < dist(X, Y)) {
Y = i;
}
}
answer(Y, location[X] + dist(X, Y), 2);
vector<int> left;
vector<int> right;
for (int i = 0; i < N; i++) {
if (i == X || i == Y) {
continue;
}
if (dist(X, i) == dist(X, Y) + dist(Y, i)) {
if (dist(Y, i) < dist(Y, X)) {
answer(i, location[Y] - dist(Y, i), 1);
}
else {
left.push_back(i);
}
}
else {
right.push_back(i);
}
}
sort(left.begin(), left.end(), cmpX);
sort(right.begin(), right.end(), cmpY);
L = X;
R = Y;
for (auto i: left) {
int B = (dist(L, i) - dist(R, i) + location[L] + location[R]) / 2;
if (btype[B] == 1) {
int A = location[L] + dist(L, i);
answer(i, A, 2);
}
else {
int A = location[R] - dist(R, i);
answer(i, A, 1);
L = i;
}
}
L = X;
R = Y;
for (auto i: right) {
int B = (dist(L, i) - dist(R, i) + location[L] + location[R]) / 2;
if (btype[B] == 2) {
int A = location[R] - dist(R, i);
answer(i, A, 1);
}
else {
int A = location[L] + dist(L, i);
answer(i, A, 2);
R = i;
}
}
}
