#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
void findLocation(int n, int first, int location[], int stype[]) {
for (int i = 0;i < n;i++) {
location[i] = -1;
stype[i] = -1;
}
location[0] = first;
stype[0] = 1;
int dist[n][n];
for (int i = 0;i < n;i++) {
for (int j = i;j < n;j++) {
if (i == j) {
dist[i][j] = INT_MAX;
continue;
}
dist[i][j] = dist[j][i] = getDistance(i, j);
}
}
int mn = INT_MAX, mnd = 0;
for (int i = 1;i < n;i++) {
if (dist[0][i] < mn) {
mn = dist[0][i];
mnd = i;
}
}
location[mnd] = first + dist[0][mnd];
stype[mnd] = 2;
vector <int> l, r;
for (int i = 1;i < n;i++) {
if (i == mnd) continue;
if (dist[0][mnd] + dist[mnd][i] == dist[0][i]) {
l.push_back(i);
continue;
}
r.push_back(i);
}
for (auto x : l) {
bool pos = false;
int loc;
for (auto y : l) {
if (x == y) continue;
if (dist[mnd][y] + dist[y][x] == dist[mnd][x]) {
pos = true;
loc = location[mnd] - dist[mnd][y] + dist[y][x];
break;
}
}
if (pos) {
location[x] = loc;
stype[x] = 2;
}
else {
location[x] = location[mnd] - dist[mnd][x];
stype[x] = 1;
}
}
for (auto x : r) {
bool pos = false;
int loc;
for (auto y : r) {
if (x == y) continue;
if (dist[0][y] + dist[y][x] == dist[0][x]) {
pos = true;
loc = location[0] + dist[0][y] - dist[y][x];
break;
}
}
if (pos) {
location[x] = loc;
stype[x] = 1;
}
else {
location[x] = location[0] + dist[0][x];
stype[x] = 2;
}
}
}
