#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int n, int first, int location[], int stype[]){
map<pair<int, int>, int>cache;
auto get = [&] (int i, int j){
if(i == j){
return 0;
}
if(i > j){
swap(i, j);
}
auto it = cache.find(make_pair(i, j));
if(it != cache.end()){
return it->second;
}
return cache[make_pair(i, j)] = getDistance(i, j);
};
location[0] = first;
int d = stype[0] = 1;
for(int i = 2; i < n; i++){
if(get(0, i) < get(0, d)){
d = i;
}
}
if(n == 1){
return;
}
stype[d] = 2;
location[d] = first + get(0, d);
vector<int>left, right;
for(int i = 1; i < n; i++){
if(i != d && get(0, i) - get(d, i) == get(0, d)){
left.emplace_back(i);
}
else if(i != d){
right.emplace_back(i);
}
}
if(!left.empty()){
sort(left.begin(), left.end(), [&] (int i, int j){
return get(d, i) < get(d, j);
});
stype[left[0]] = 1;
location[left[0]] = location[d] - get(d, left[0]);
for(int i = 1, p = 0; i < left.size(); i++){
if(get(left[p], left[i]) == get(d, left[i]) - get(d, left[p])){
stype[left[i]] = 2;
location[left[i]] = location[left[p]] + get(left[p], left[i]);
}
else{
stype[left[p = i]] = 1;
location[left[i]] = location[d] - get(d, left[i]);
}
}
}
if(!right.empty()){
sort(right.begin(), right.end(), [&] (int i, int j){
return get(d, i) < get(d, j);
});
stype[right[0]] = 2;
location[right[0]] = first + get(0, right[0]);
for(int i = 1, p = 0; i < right.size(); i++){
if(get(right[p], right[i]) == get(d, right[i]) - get(d, right[p])){
stype[right[i]] = 1;
location[right[i]] = location[right[p]] - get(right[p], right[i]);
}
else{
stype[right[p = i]] = 2;
location[right[i]] = first + get(0, right[i]);
}
}
}
}
