#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[])
{
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);
}
location[0] = first;
stype[0] = 1;
location[clos[0]] = first+dist[clos[0]][0];
stype[clos[0]] = 2;
for(int i = 0; i < N; i++)
{
if(i == 0 || i == clos[0]) continue;
if(dist[0][i] < dist[clos[0]][i])
{
if(0 != clos[i] && dist[0][clos[i]] < dist[0][i])
{
location[i] = first+dist[0][clos[i]]-dist[i][clos[i]];
stype[i] = 1;
// printf("KANAN BAWAH %d %d\n", i, location[i]);
}
else
{
location[i] = first+dist[0][i];
stype[i] = 2;
// printf("KANAN ATAS %d %d\n", i, location[i]);
}
}
else
{
if(clos[0] != clos[i] && dist[0][clos[i]] < dist[0][i])
{
location[i] = location[clos[0]]-dist[clos[0]][clos[i]]+dist[i][clos[i]];
stype[i] = 2;
// printf("KIRI ATAS %d %d\n", i, location[i]);
}
else
{
location[i] = location[clos[0]]-dist[clos[0]][i];
stype[i] = 1;
// printf("KIRI BAWAH %d %d\n", i, location[i]);
}
}
}
// printf("ANS : \n");
// for(int i = 0; i < N; i++)
// printf(" %d %d\n", location[i], stype[i]);
}
