#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
int ask(int i, int j) {
return getDistance(i,j);
}
void findLocation(int n, int p, int ans[], int type[]) {
if (n==1) {
ans[0]=p, type[0]=1; return;
}
vector<int> a(n), b(n), c(n);
vector<int> vis(n,0); vis[0]=1;
int f=0,s=1;
forn(i,n) {
if (vis[i]) continue;
a[i]=ask(0,i);
if (a[i] < a[s]) s=i;
}
vis[s]=1;
b[0]=a[s];
forn(i,n) {
if (vis[i]) continue;
b[i]=ask(s,i);
if (b[i]<b[f]) f=i;
}
vis[f]=1;
ans[0]=p, type[0]=1;
ans[s]=p+a[s], type[s]=2;
ans[f]=ans[s]-b[f], type[f]=1;
vector<pi> l,r;
c[0]=a[f], c[s]=b[f];
forn(i,n) {
if (vis[i]) continue;
int x=a[i], y=b[i], z=b[f];
if (x==a[s]+y) {
l.pb({y,i});
c[i]=y+z;
} else if (y==x-a[s]+2*z) {
r.pb({y-z,i});
c[i]=y-z;
} else assert(0);
}
sort(all(r));
sort(all(l));
int u,v;
u=f, v=s;
for(auto&it:r) {
int d=it.f, i=it.s;
int x=d, y=ask(v,i);
int m=v;
forn(j,n) {
if (!vis[j]) continue;
if (type[j]!=2) continue;
if (ans[j] < ans[v]-y) continue;
if (ans[j] < ans[m]) m=j;
}
if (x == ans[m]-ans[u]+ans[m]-(ans[v]-y)) {
type[i]=1;
ans[i]=ans[v]-y;
} else {
type[i]=2;
ans[i]=ans[u]+x;
v=i;
}
vis[i]=1;
}
u=f,v=s;
for(auto&it:l) {
int d=it.f, i=it.s;
int x=d, y=ask(u,i);
int m=u;
forn(j,n) {
if (!vis[j]) continue;
if (type[j]!=1) continue;
if (ans[j] > ans[u]+y) continue;
if (ans[j] > ans[m]) m=j;
}
if (x == ans[v]-ans[m]+(ans[u]+y)-ans[m]) {
type[i]=2;
ans[i]=ans[u]+y;
} else {
type[i]=1;
ans[i]=ans[v]-x;
u=i;
}
vis[i]=1;
}
}
