#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int TYPE_C = 1, TYPE_D = 2;
const int INF = 1e9;
const int MAX = 5000;
template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
if (x > y) { x = y; return true; }
return false;
}
int N, dist[MAX][MAX];
int getMinIndex(int x) {
int cur_d = INF, y = -1;
for (int i = 0; i < N; i++) if (i != x)
if (minimise(cur_d, dist[x][i]))
y = i;
return y;
}
void findLocation(int _N, int s0, int s[], int t[]) {
N = _N;
s[0] = s0;
t[0] = TYPE_C;
for (int i = 0; i < N; i++) {
dist[i][i] = 0;
for (int j = i + 1; j < N; j++)
dist[i][j] = dist[j][i] = getDistance(i, j);
}
int y = getMinIndex(0);
int x = getMinIndex(y);
s[y] = s[0] + dist[0][y];
t[y] = TYPE_D;
s[x] = s[y] - dist[x][y];
t[x] = TYPE_C;
vector<int> lefts = (x == 0 ? vector<int>{0} : vector<int>{0, x}), rights = {y};
for (int i = 1; i < N; i++) if (i != x and i != y) {
if (dist[x][i] > dist[y][i])
lefts.push_back(i);
else
rights.push_back(i);
}
for (int i : lefts) {
t[i] = TYPE_C;
s[i] = s[y] - dist[y][i];
}
for (int i : rights) {
t[i] = TYPE_D;
s[i] = s[x] + dist[x][i];
}
for (int i : rights) for (int j : rights) if (i != j) {
if (dist[i][x] - dist[j][x] == dist[i][j]) {
t[i] = TYPE_C;
t[j] = TYPE_D;
s[j] = s[x] + dist[j][x];
s[i] = s[j] - dist[j][i];
}
}
for (int i : lefts) for (int j : lefts) if (i != j) {
if (dist[i][y] - dist[j][y] == dist[i][j]) {
t[i] = TYPE_D;
t[j] = TYPE_C;
s[j] = s[y] - dist[j][y];
s[i] = s[j] + dist[j][i];
}
}
}
