#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
const int MAXN = 5010;
int dist[MAXN][MAXN];
vector<pair<int, int> > leftBlocks, rightBlocks;
void get(int i, int j)
{
if(dist[i][j] != -1) return;
dist[i][j] = dist[j][i] = getDistance(i, j);
}
void findLocation(int n, int first, int location[], int stype[])
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dist[i][j] = (i == j) ? 0 : -1;
int L = 0, R = 0;
for(int i = 1; i < n; i++)
{
get(0, i);
if(!R || dist[0][i] < dist[0][R]) R = i;
}
location[0] = first;
location[R] = first + dist[0][R];
stype[0] = 1;
stype[R] = 2;
for(int i = 1; i < n; i++)
{
if(i == R) continue;
get(R, i);
if(dist[R][i] < dist[R][L]) L = i;
}
location[L] = location[R] - dist[R][L];
stype[L] = 1;
for(int i = 1; i < n; i++)
dist[L][i] = dist[0][i] - (dist[0][R] - dist[L][R]);
for(int i = 0; i < n; i++)
{
if(i == L || i == R) continue;
if(dist[L][i] < dist[R][i])
rightBlocks.push_back({dist[L][i], i});
else
leftBlocks.push_back({dist[R][i], i});
}
sort(leftBlocks.begin(), leftBlocks.end());
sort(rightBlocks.begin(), rightBlocks.end());
int R2 = R;
for(int i = 0; i < (int) rightBlocks.size(); i++)
{
int id = rightBlocks[i].second;
int d = rightBlocks[i].first;
get(R, id);
if(d - dist[L][R] == dist[id][R])
{
location[id] = location[R] - dist[id][R];
stype[id] = 1;
}
else
{
location[id] = location[L] + d;
stype[id] = 2;
R = id;
}
}
R = R2;
for(int i = 0; i < (int) leftBlocks.size(); i++)
{
int id = leftBlocks[i].second;
int d = leftBlocks[i].first;
get(L, id);
if(d - dist[L][R] == dist[L][id])
{
location[id] = location[L] + dist[id][L];
stype[id] = 2;
}
else
{
location[id] = location[R] - d;
stype[id] = 1;
L = id;
}
}
}
