#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <assert.h>
#include "rail.h"
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
const int INF = 1e9;
int dist[5003][5003];
int clos[5003];
int cntt = 0;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
if(N == 1)
return;
for(int i = 0; i < N; i++)
{
clos[i] = INF;
for(int j = i+1; j < N; j++)
{
dist[i][j] = getDistance(i,j);
++cntt;
dist[j][i] = dist[i][j];
}
}
if(cntt > N*(N-1)/2)
{
assert(0);
}
if(N > 5000)
assert(0);
// for(int i = 0; i < N; i++)
// {
// for(int j = 0; j < N; j++)
// printf("%d ", dist[i][j]);
// printf("\n");
// }
for(int i = 0; i < N; i++)
{
int mn = 1e9;
for(int j = 0; j < N; j++)
{
if(i != j && mn > dist[i][j])
{
mn = dist[i][j];
clos[i] = j;
}
}
// printf("%d %d %d\n", i, clos[i], mn);
}
int a = clos[clos[0]];
location[clos[0]] = first+dist[clos[0]][0];
stype[clos[0]] = 2;
location[a] = location[clos[a]]-dist[a][clos[a]];
stype[a] = 1;
if(a != clos[clos[a]])
assert(0);
for(int i = 0; i < N; i++)
{
if(i == a || i == clos[a] || i == 0) continue;
if(dist[a][i] < dist[clos[a]][i])
{
if(a != clos[i] && dist[a][clos[i]] < dist[a][clos[clos[i]]])
{
location[i] = location[a]+dist[a][clos[i]]-dist[i][clos[i]];
stype[i] = 1;
// printf("KANAN BAWAH %d %d\n", i, location[i]);
}
else
{
location[i] = location[a]+dist[a][i];
stype[i] = 2;
// printf("KANAN ATAS %d %d\n", i, location[i]);
}
}
else
{
if(clos[a] != clos[i] && dist[a][clos[i]] < dist[a][clos[clos[i]]])
{
location[i] = location[clos[a]]-dist[clos[a]][clos[i]]+dist[i][clos[i]];
stype[i] = 2;
// printf("KIRI ATAS %d %d\n", i, location[i]);
}
else
{
location[i] = location[clos[a]]-dist[clos[a]][i];
stype[i] = 1;
// printf("KIRI BAWAH %d %d\n", i, location[i]);
}
}
}
// printf("ANS : %d %d\n", a, location[a]);
// for(int i = 0; i < N; i++)
// printf(" %d %d\n", location[i], stype[i]);
}
