#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];
const int maxs = 4e6+5;
int typ[maxs];
bool cmp1(int a, int b)
{
return dist0[a]< dist0[b];
}
bool cmp2(int a, int b)
{
return distu[a]< distu[b];
}
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
typ[first] = 1;
stype[0] = 1;
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;
location[u] = first+dist0[u];
stype[u] = 2;
typ[location[u]] = 2;
distu[0] = dist0[u];
vector<int> tol, tor;
printf("u = %d\n", u);
for(int i = 1; i< N; i++)
{
if(i == u) continue;
distu[i] = getDistance(u, i);
if(dist0[i] == dist0[u]+distu[i])
{
if(distu[i]< dist0[u])
{
tor.pb(i);
}
else tol.pb(i);
}
else tor.pb(i);
}
sort(tor.begin(), tor.end(), cmp1);
int y = u;
for(int z : tor)
{
int k = dist0[z]-dist0[y]-getDistance(y, z);
k = -k;
k /= 2;
// printf("for %d to be type 1 there must be 2 at %d\n", z, location[y]-k);
if(typ[location[y]-k] == 2)
{
//type c
int mid = location[y]-k;
assert(dist0[z]> mid-first);
location[z] = mid-(dist0[z]-(mid-first));
// printf("location[%d] = %d\n", z, location[z]);
typ[location[z]] = 1;
stype[z] = 1;
}
else
{
//type d
location[z] = first+dist0[z];
typ[location[z]] = 2;
stype[z] = 2;
y = z;
}
}
y = 0;
sort(tol.begin(), tol.end(), cmp2);
for(int z : tol)
{
int k = distu[z]-distu[y]-getDistance(y, z);
k = -k;
k /= 2;
if(typ[location[y]+k] == 1)
{
//type d
int mid = location[y]+k;
location[z] = mid+(distu[z]-(location[u]-mid));
typ[location[z]] = 2;
stype[z] = 2;
}
else
{
//type c
location[z] = location[u]-distu[z];
typ[location[z]] = 1;
stype[z] = 1;
y = z;
}
}
// for(int i = 0; i< n; i++) printf("%d %d\n", stype[i], location[i]);
}
