#include "rail.h"
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std ;
#define ff first
#define ss second
#define pb push_back
typedef pair<int,int> ii ;
int dist[5010][5010] ;
void findLocation(int N, int first, int location[], int stype[])
{
vector <ii> fromA, fromA2 ;
for ( int i = 1 ; i < N ; ++i ) {
int x = getDistance ( 0, i );
dist[0][i] = dist[i][0] = x ;
fromA.pb ( {x, i} ) ;
}
set <int> befA, aftA ;
sort ( fromA.begin(), fromA.end() ) ;
int j = fromA[0].ss ;
for ( int i = 0 ; i < N ; ++i ) {
int x = getDistance ( i, j ) ;
dist[i][j] = dist[j][i] = x ;
if ( i == 0 ) {}
else if ( x < dist[0][j] ) aftA.insert ( i ) ;
else if ( dist[0][i] < x ) aftA.insert ( i ) ;
else befA.insert ( i ) ;
fromA2.pb ( {x, i} ) ;
}
sort ( fromA2.begin(), fromA2.end() ) ;
location[0] = first ;
stype[0] = 1 ;
int c = -1 ;
for ( auto i:fromA ) {
if ( !aftA.count ( i.ss ) ) continue ;
if ( c == -1 ) c = i.ss, location[c] = location[0] + i.ff, stype[c] = 2 ;
else {
int x = getDistance ( i.ss, c ) ;
if ( dist[0][i.ss] < x ) c = i.ss, location[c] = location[0] + i.ff, stype[c] = 2 ;
else location[i.ss] = location[c] - x, stype[i.ss] = 1 ;
}
}
c = -1 ;
for ( auto i:fromA2 ) {
if ( !befA.count ( i.ss ) ) continue ;
if ( c == -1 ) c = i.ss, location[c] = location[j] - i.ff, stype[c] = 1 ;
else {
int x = getDistance ( i.ss, c ) ;
if ( dist[j][i.ss] < x ) c = i.ss, location[c] = location[0] - i.ff, stype[c] = 1 ;
else location[i.ss] = location[c] + x, stype[i.ss] = 2 ;
}
}
return ;
}
