#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;
bitset<5050> mark;
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];
if (!mark[e]) {
stype[e] = 1;
location[e] = location[ONE] - dist[1][e];
rep(j , i + 1 , le.size())
if (getDistance(le[j] , e) + dist[1][e] == dist[1][le[j]]) {
mark[le[j]] = true;
stype[le[j]] = 2;
location[le[j]] = location[e] + dist[1][le[j]] - dist[1][e];
}
}
}
}
{
sort(all(ri) , [](int a, int b) { return dist[0][a] < dist[0][b]; });
rep(i , 0 , ri.size()) {
int e = ri[i];
if (!mark[e]) {
stype[e] = 2;
location[e] = location[0] + dist[0][e];
rep(j , i + 1 , ri.size())
if (getDistance(ri[j] , e) + dist[0][e] == dist[0][ri[j]]) {
mark[ri[j]] = true;
stype[ri[j]] = 1;
location[ri[j]] = location[e] - dist[0][ri[j]] + dist[0][e];
}
}
}
}
return;
}
