#include "rail.h"
#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
void findLocation(signed n, signed first, signed location[], signed stype[]){
stype[0] = 1;
location[0] = first;
int loc0[n], locD[n], locC[n];
int firstD, firstC, distD = inf, distC = inf;
for (int i = 0; i < n; i++){
if (i == 0) loc0[i] = 0;
else loc0[i] = getDistance(0, i);
}
// sort by least
for (int i = 0; i < n; i++){
if (i == 0) continue;
if (distD > loc0[i]){
distD = loc0[i];
firstD = i;
}
}
for (int i = 0; i < n; i++){
if (i == firstD) locD[i] = 0;
else locD[i] = getDistance(firstD, i);
}
// sort by least
for (int i = 0; i < n; i++){
if (i == firstD) continue;
if (distC > locD[i]){
distC = locD[i];
firstC = i;
}
}
for (int i = 0; i < n; i++){
if (i == firstC) locC[i] = 0;
else locC[i] = getDistance(firstC, i);
}
// find the distances between each station
stype[firstC] = 1;
stype[firstD] = 2;
location[firstD] = location[0] + distD;
location[firstC] = location[firstD] - distC;
for (int i = 0; i < n; i++){
if (i == 0 || i == firstC || i == firstD) continue;
if (locC[i] > locD[i]){
// then it is a C type
stype[i] = 1;
location[i] = location[firstD] - locD[i];
}
else{
stype[i] = 2;
location[i] = location[firstC] + locC[i];
}
}
}
