#include <bits/stdc++.h>
#include "rail.h"
#define MP make_pair
#define ad push_back
#define sc second
#define fr first
using namespace std;
const int m = 1e6 + 10;
int n, fr, sm, sc;
int a[5010][5010];
pair<int, int> b[m];
bool col[5010];
int getmn(int aa)
{
int mn = INT_MAX, ret = aa;
for (int i = 0; i < n; i++)
{
if(aa == i) continue;
if(a[aa][i] < mn) mn = a[aa][i], ret = i;
}
return ret;
}
vector <pair<int, int> > fp;
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
fr = first;
for (int i = 1; i < n; i++)
a[0][i] = a[i][0] = getDistance(0, i);
stype[0] = 1, location[0] = fr;
if(n == 1) return;
sm = getmn(0), sc = a[0][sm] + fr;
stype[sm] = 2, location[sm] = sc;
for (int i = 1; i < n; i++)
if(i != sm) a[i][sm] = a[sm][i] = getDistance(i, sm);
for (int i = 1; i < n; i++)
{
if(i == sm) continue;
if(a[0][sm] + a[sm][i] == a[0][i])
{
if(a[sm][i] < a[0][sm]) stype[i] = 1, location[i] = sc - a[i][sm], col[i] = true;
else fp.ad(MP(a[sm][i], i));
}
}
sort(fp.begin(), fp.end());
col[0] = col[sm] = 1;
int ss = 0;
for(auto p : fp)
{
int d = getDistance(ss, p.sc);
int mx = ss;
for (int i = 0; i < n; i++){
if(col[i] && location[i] < d + location[ss] && stype[i] == 1)
{
if(location[mx] < location[i]) mx = i;
}}
if(d - location[mx] + location[ss] + a[mx][sm] == a[sm][p.sc])
{
stype[p.sc] = 2;
location[p.sc] = d + location[ss];
col[p.sc] = 1;
}
else
{
stype[p.sc] = 1;
location[p.sc] = sc - a[sm][p.sc];
col[p.sc] = 1;
ss = p.sc;
}
}
fp.clear();
for (int i = 1; i < n; i++)
{
if(i == sm) continue;
if(a[0][sm] + a[sm][i] != a[0][i])
{
fp.ad(MP(a[sm][i], i));
}
}
sort(fp.begin(), fp.end());
ss = sm;
for(auto p : fp)
{
int d = getDistance(ss, p.sc);
int mx = ss;
for (int i = 0; i < n; i++)
{
if(col[i] && location[i] > location[ss] - d && stype[i] == 2)
{
if(location[mx] > location[i]) mx = i;
}
}
if(d - location[ss] + location[mx] + a[0][mx] == a[0][p.sc])
{
stype[p.sc] = 1;
location[p.sc] = location[ss] - d;
col[p.sc] = 1;
}
else
{
stype[p.sc] = 2;
location[p.sc] = location[0] + a[0][p.sc];
col[p.sc] = 1;
ss = p.sc;
}
}
return;
}
