#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
} else {
return false;
}
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
} else {
return false;
}
}
constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;
void findLocation(int n, int first, int location[], int stype[]) {
Vec<Vec<i32>> dist(n, Vec<i32>(n, 0));
REP(i, n) REP(j, i) {
dist[i][j] = dist[j][i] = getDistance(i, j);
}
Vec<i32> mn(n, INF), mnrg(n, 0);
REP(i, n) {
REP(j, n) {
if (i != j && chmin(mn[i], dist[i][j])) {
mnrg[i] = j;
}
}
}
i32 y = mnrg[0];
i32 x = mnrg[y];
stype[x] = 1;
location[x] = first + mn[0] - mn[y];
stype[y] = 2;
location[y] = first + mn[0];
REP(i, n) {
if (i == x || i == y) {
continue;
}
if (dist[i][x] < dist[i][y]) {
continue;
}
if (mnrg[i] != y && dist[i][mnrg[i]] + dist[mnrg[i]][y] == dist[i][y]) {
continue;
}
stype[i] = 1;
location[i] = location[y] - dist[i][y];
}
REP(i, n) {
if (i == x || i == y) {
continue;
}
if (dist[i][x] < dist[i][y]) {
continue;
}
if (mnrg[i] != y && dist[i][mnrg[i]] + dist[mnrg[i]][y] == dist[i][y]) {
stype[i] = 2;
location[i] = location[mnrg[i]] + mn[i];
}
}
REP(i, n) {
if (i == x || i == y) {
continue;
}
if (dist[i][x] > dist[i][y]) {
continue;
}
if (mnrg[i] != x && dist[i][mnrg[i]] + dist[mnrg[i]][x] == dist[i][x]) {
continue;
}
stype[i] = 2;
location[i] = location[x] + dist[i][x];
}
REP(i, n) {
if (i == x || i == y) {
continue;
}
if (dist[i][x] > dist[i][y]) {
continue;
}
if (mnrg[i] != x && dist[i][mnrg[i]] + dist[mnrg[i]][x] == dist[i][x]) {
stype[i] = 1;
location[i] = location[mnrg[i]] - mn[i];
}
}
}
