#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mp;
int _dist[5001][5001];
int dist(int a, int b){
if (_dist[a][b]==-1) _dist[a][b]=getDistance(a,b);
return _dist[a][b];
}
void findLocation(int N, int first, int location[], int stype[])
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j){
_dist[i][j]=-1;
if (i==j) _dist[i][j]=0;
}
}
int c = 0, d = 1;
for (int i = 2; i < N; i++){
if (dist(c,i)<dist(c,d)) d=i;
}
vector<int> left;
vector<int> right;
stype[c]=1,stype[d]=2;
location[c]=first,location[d]=first+dist(c,d);
for (int i = 0; i < N; i++){
if (i==c || i==d) continue;
if (dist(c,i)==dist(c,d)+dist(d,i)){
if (dist(d,i)<dist(c,d)){
location[i]=location[d]-dist(d,i);
stype[i]=1;
}
else left.push_back(i);
}
else {
right.push_back(i);
}
}
sort(left.begin(), left.end(), [&](int a, int b){
return dist(d,a)<dist(d,b);
});
sort(right.begin(), right.end(), [&](int a, int b){
return dist(c,a)<dist(c,b);
});
if (left.size()){
set<int> virt;
int fiC = left[0];
location[fiC]=location[d]-dist(d,fiC);
stype[fiC]=1;
virt.insert(location[fiC]);
for (int _ = 1; _ < left.size(); _++){
int v = left[_];
int vloc = location[fiC]+dist(fiC,v);
int hh = dist(d,v)-(location[d]-vloc);
if (hh%2 || virt.find(vloc-hh/2)==virt.end()){
stype[v]=1;
location[v]=location[d]-dist(d,v);
fiC = v;
virt.insert(location[fiC]);
}
else {
stype[v]=2;
location[v]=vloc;
}
}
}
if (right.size()){
set<int> virt;
int fiD = right[0];
location[fiD]=location[c]+dist(c,fiD);
stype[fiD]=2;
virt.insert(location[fiD]);
for (int _ = 1; _ < right.size(); _++){
int v = right[_];
int vloc = location[fiD]-dist(fiD,v);
int hh = dist(c,v)-(vloc-location[c]);
if (hh%2 || virt.find(vloc+hh/2)==virt.end()){
stype[v]=2;
location[v]=location[c]+dist(c,v);
fiD = v;
virt.insert(location[fiD]);
}
else {
stype[v]=1;
location[v]=vloc;
}
}
}
}
