#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
using namespace std;
const int N = 5005;
int ar[N][N], in[N], u[N];
vector < pair <int, int> > vec;
void findLocation(int n, int First, int ans[], int type[])
{
type[0] = 1;
ans[0] = First;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
ar[i][j] = getDistance(i, j);
ar[j][i] = ar[i][j];
}
}
for (int i = 0; i < n; i++)
{
in[i] = (i + 1) % n;
for (int j = 0; j < n; j++)
{
if (i == j) continue;
if ( ar[i][in[i]] > ar[i][j] )
in[i] = j;
}
}
type[ in[0] ] = 2;
ans[ in[0] ] = First + ar[0][ in[0] ];
u[0] = u[ in[0] ] = 1;
for (int i = 1; i < n; i++)
{
if (u[i]) continue;
vec.pb( mk(i, in[i]) );
u[i] = u[ in[i] ] = 1;
}
for (auto it : vec)
{
if (type[it.fr] == 1)
{
type[it.sc] = 2;
ans[it.sc] = ans[it.fr] + ar[it.fr][it.sc];
continue;
}
if(type[it.sc] == 1)
{
type[it.fr] = 2;
ans[it.fr] = ans[it.sc] + ar[it.fr][it.sc];
continue;
}
if (type[it.fr] == 2)
{
type[it.sc] = 1;
ans[it.sc] = ans[it.fr] - ar[it.fr][it.sc];
continue;
}
if (type[it.sc] == 2)
{
type[it.fr] = 1 ;
ans[it.fr] = ans[it.sc] - ar[it.fr][it.sc];
continue;
}
if ( ar[0][it.fr] > ar[0][it.sc] ) swap(it.fr, it.sc);
if (ar[0][it.fr] < ar[in[0]][it.fr])
{
type[ it.fr ] = 2;
ans[ it.fr ] = First + ar[0][it.fr];
type[it.sc] = 1;
ans[ it.sc ] = ans[ it.fr ] - ar[it.fr][it.sc];
}
else
{
type[ it.fr ] = 1;
ans[ it.fr ] = First + ar[0][in[0]] - ar[it.fr][in[0]];
type[it.sc] = 2;
ans[ it.sc ] = ans[ it.fr ] + ar[it.fr][it.sc];
}
}
// cout << endl;
// for (int i = 0; i < n; i++)
// {
// cout <<type[i] << " " << ans[i] << endl;
// }
}
