#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()
int dist[2][5010];
vector<int> le, ri;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
if (N == 1) return;
rep(i , 1 , N)
dist[0][i] = getDistance(0 , i);
int ONE = min_element(dist[0] + 1 , dist[0] + N) - dist[0];
location[ONE] = first + dist[0][ONE];
stype[ONE] = 2;
rep(i , 0 , N)
dist[1][i] = getDistance(i , ONE);
le.pb(0);
rep(i , 1 , N)
if (i != ONE) {
if (dist[0][i] > dist[1][i])
le.pb(i);
else
ri.pb(i);
}
{
sort(all(le) , [](int a , int b) { return dist[1][a] < dist[1][b]; });
int last = le[0];
location[last] = location[ONE] - dist[1][last];
stype[last] = 1;
rep(i ,1 , le.size()) {
int e = le[i];
int me = getDistance(last , e);
if (me != dist[1][e] - dist[1][last]) {
last = e;
stype[last] = 1;
location[last] = location[ONE] - dist[1][last];
}
else {
stype[e] = 2;
location[e] = location[last] + me;
}
}
}
{
sort(all(ri) , [](int a, int b) { return dist[0][a] < dist[0][b]; });
int last = ONE;
rep(i , 0 , ri.size()) {
int e = ri[i];
int me = getDistance(last , e);
if (me != dist[0][e] - dist[0][last]) {
last = e;
stype[last] = 2;
location[last] = location[0] + dist[0][last];
}
else {
stype[e] = 1;
location[e] = location[last] - me;
}
}
}
return;
}
