#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[])
{
map< ll,ll> mp;
location[0] = first,stype[0] = 1;
mp[location[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;
mp[location[a]] = 2;
// cout<<a<<' '<<location[a]<<'\n';
for (ll i = 1;i < n;i ++){
if (i != a)dista[i] = getDistance(a,i);
}
dista[0] = dist0[a];
vector <ll> all0,alla;
for (ll i = 1;i < n;i ++){
if (i != a){
if (dist0[i] != dista[i] + dist0[a])all0.push_back(i);
else alla.push_back(i);
}
}
sort(all0.begin(),all0.end(),[&](ll x,ll y){return dist0[x] < dist0[y];});
// map <ll,ll> mp;
for (ll i = 0;i < sz(all0);i ++){
ll j = i;
location[all0[i]] = dist0[all0[i]]+location[0];
stype[all0[i]] = 2;
mp[location[all0[i]]] = 2;
while (j + 1 < sz(all0)){
ll dick = getDistance(all0[i],all0[j+1]);
// if (all0[j+1]==6){
// cout<<dist0[all0[i]]<<' '<<dick<<' '<<dist0[all0[j+1]]<<'\n';
// }
if (dist0[all0[i]] + dick == dist0[all0[j+1]] || mp[location[all0[i]] - (dist0[all0[i]] + dick - dist0[all0[j+1]])/2] == 2){
j++;
location[all0[j]] = location[all0[i]] - dick;
stype[all0[j]] = 1;
mp[location[all0[j]]] = 1;
}
else{
break;
}
}
i = j;
}
// alla.push_back(0);
sort(alla.begin(),alla.end(),[&](ll x,ll y){return dista[x] < dista[y];});
// for (auto x:alla)cout<<x<<' ';
// cout<<'\n';
for (ll i = 0;i < sz(alla);i ++){
// cout<<alla[i]<<'\n';
ll j = i;
location[alla[i]] = -dista[alla[i]]+location[a];
stype[alla[i]] = 1;
mp[location[alla[i]]] = 1;
// cout<<alla[i]<<'\n';
while (j + 1 < sz(alla)){
ll dick = getDistance(alla[i],alla[j+1]);
// cout<<alla[i]<<' '<<alla[j+1]<<' '<<dick<<' '<<location[alla[i]] + (dist0[alla[i]] + dick - dist0[alla[j+1]])/2<<'\n';
if (dista[alla[i]] + dick == dista[alla[j+1]] || mp[location[alla[i]] + (dista[alla[i]] + dick - dista[alla[j+1]])/2] == 1){
j++;
location[alla[j]] = location[alla[i]] + dick;
stype[alla[j]] = 2;
mp[location[alla[j]]] = 2;
}
else{
break;
}
}
i = j;
}
// for (ll j = 0;j < n; j++){
// cout<<stype[j]<<' '<<location[j]<<'\n';
// }
}
