#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
namespace{
const ll MAXN = 5e3+5;
ll n;
ll dist0[MAXN];
ll dista[MAXN];
ll a;
}
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first,stype[0] = 1;
if (n==1){
return;
}
n = N;
for (ll i = 1;i < n;i ++){
dist0[i] = getDistance(0,i);
}
a = 1;
for (ll i = 1;i < n;i ++){
if (dist0[i] < dist0[a])a=i;
}
location[a] = location[0] + dist0[a];
stype[a] = 2;
// cout<<a<<' '<<location[a]<<'\n';
for (ll i = 1;i < n;i ++){
if (i != a)dista[i] = getDistance(a,i);
}
vector <ll> all0,alla;
for (ll i = 1;i < n;i ++){
if (i != a){
if (dist0[i] < dista[i])all0.push_back(i);
else alla.push_back(i);
}
}
sort(all0.begin(),all0.end(),[&](ll x,ll y){return dist0[x] < dist0[y];});
for (ll i = 0;i < sz(all0);i ++){
ll j = i;
location[all0[i]] = dist0[all0[i]]+location[0];
stype[all0[i]] = 2;
while (j + 1 < sz(all0)){
ll dick = getDistance(all0[i],all0[j+1]);
if (dick + dist0[all0[i]] == dist0[all0[j+1]]){
j++;
location[all0[j]] = location[all0[i]] - dick;
stype[all0[j]] = 1;
}
else{
break;
}
}
i = j;
}
sort(alla.begin(),alla.end(),[&](ll x,ll y){return dista[x] < dista[y];});
for (ll i = 0;i < sz(alla);i ++){
ll j = i;
location[alla[i]] = -dista[alla[i]]+location[a];
stype[alla[i]] = 1;
while (j + 1 < sz(alla)){
ll dick = getDistance(alla[i],alla[j+1]);
if (dick + dista[alla[i]] == dista[alla[j+1]]){
j++;
location[alla[j]] = location[alla[i]] + dick;
stype[alla[j]] = 2;
}
else{
break;
}
}
i = j;
}
// for (ll j = 0;j < n; j++){
// cout<<stype[j]<<' '<<location[j]<<'\n';
// }
}
