#include "rail.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
int n;
const int maxn = 5005;
int dist0[maxn];
int distu[maxn];
int distr[maxn];
int distl[maxn];
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
ii near = {1e9, 0};
for(int i = 1; i< n; i++)
{
dist0[i] = getDistance(0, i);
near = min(near, {dist0[i], i});
}
int u = near.Y;
vector<int> tol, tor;
tor.pb(u);
for(int i = 1; i< n; i++)
{
if(i == u) continue;
distu[i] = getDistance(u, i);
if(distu[i]> dist0[i]) tor.pb(i);
else tol.pb(i);
}
ii far = {0, 0};
for(int x : tor)
{
far = max(far, {dist0[x], x});
}
int T = far.Y, xt = far.X;
for(int x : tor)
{
if(x == u)
{
distr[u] = distu[T];
}
else distr[x] = getDistance(T, x);
}
distr[0] = dist0[T];
int buff = 0;
while(!tor.empty())
{
ii close = {1e9, 0};
vector<int> bad;
for(int x : tor)
{
close = min(close, {dist0[x], x});
}
int tag = close.Y;
location[tag] = dist0[tag];
stype[tag] = 2;
bool last = false;
if(distr[tag] == xt-location[tag])
{
T = tag;
xt = location[tag];
last = true;
}
for(int x : tor)
{
if(x == tag) continue;
int calc = dist0[x]-location[tag];
calc = location[tag]-calc;
if(buff< calc && calc< location[tag])
{
if(last || distr[x] == xt + dist0[x] - 2*location[tag])
{
location[x] = calc;
stype[x] = 1;
}
else
{
bad.pb(x);
}
}
else bad.pb(x);
}
buff = location[tag];
tor = bad;
}
far = {0, 0};
for(int x : tol)
{
far = max(far, {dist0[x], x});
}
T = far.Y, xt = -(far.X-2*dist0[u]);
for(int x : tol)
{
distl[x] = getDistance(T, x);
}
distl[0] = dist0[T];
buff = 0;
while(!tol.empty())
{
ii close = {1e9, 0};
vector<int> bad;
for(int x : tol)
{
close = min(close, {dist0[x], x});
}
int tag = close.Y;
// printf("tag = %d\n", tag);
location[tag] = -(dist0[tag]-2*dist0[u]);
stype[tag] = 1;
bool last = false;
if(distl[tag] == location[tag]-xt)
{
T = tag;
xt = location[tag];
last = true;
}
for(int x : tol)
{
if(x == tag) continue;
int calc = (dist0[x]-2*dist0[u]);
int rem = calc+location[tag];
calc = location[tag]+rem;
// printf("calc = %d\n", calc);
if(location[tag]< calc && calc< buff)
{
// if(tag == 1 && x == 7) printf("%d == %d\n", distl[x], dist0[x]-2*location[u]+2*location[tag]-xt);
if(last || distl[x] == dist0[x]-2*location[u]+2*location[tag]-xt)
{
location[x] = calc;
// printf("det %d->%d\n", x, location[x]);
stype[x] = 2;
}
else
{
bad.pb(x);
}
}
else bad.pb(x);
}
buff = location[tag];
tol = bad;
}
// for(int i = 0; i< N; i++) printf("%d %d\n", stype[i], location[i]);
for(int i = 0; i< N; i++) location[i] += first;
stype[0] = 1;
}
