#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] ;
vector <ii> vec[5010] ;
void findLocation(int N, int first, int location[], int stype[])
{
for ( int i = 0 ; i < N ; ++i ) {
for ( int j = i+1 ; j < N; ++j ) {
int x = getDistance ( i, j ) ;
dist[i][j] = dist[j][i] = x ;
if ( i == 0 || vec[i].size() == 0) vec[i].pb ({x,j}) ;
else vec[i][0] = min ( vec[i][0], {x,j} ) ;
if ( j == 0 || vec[j].size() == 0 ) vec[j].pb ({x,i}) ;
else vec[j][0] = min ( vec[j][0], {x, i} ) ;
}
}
for ( int i = 0 ; i < N ; ++i )
sort ( vec[i].begin(), vec[i].end()) ;
set <int> befA, aftA ;
vector <ii> fromA = vec[0], fromA2 ;
int j = fromA[0].ss, pc = fromA[0].ff ;
for ( int i = 0 ; i < N ; ++i ) {
if ( i == j ) continue ;
int x = dist[i][j] ;
fromA2.pb ( {x, i} ) ;
}
sort ( fromA2.begin(), fromA2.end() ) ;
pc -= fromA2[0].ff ;
for ( int i = 0 ; i < N ; ++i ) {
int x = dist[i][j] ;
if ( i == 0 || x < dist[0][j] || dist[0][i] - pc < x ) {}
else befA.insert ( i ) ;
}
// return ;
location[0] = first ; stype[0] = 1 ;
for ( int i = 0 ; i+1 < N ; ++i ) {
if ( befA.count(vec[0][i].ss) || location[vec[0][i].ss] != 0) continue ;
location[vec[0][i].ss] = location[0] + vec[0][i].ff ;
stype[vec[0][i].ss] = 2 ;
for ( int k = 0 ; k < N ; ++k ) {
if ( location[k] != 0 ) continue ;
if ( stype[vec[k][0].ss] == 2 )
stype[k] = 1, location[k] = location[vec[k][0].ss] - vec[k][0].ff ;
}
}
vec[j].clear() ;
for ( int i = 0 ; i+1 < N ; ++i ) {
vec[j].pb ( fromA2[i] ) ;
if ( !befA.count(vec[j][i].ss) || location[vec[j][i].ss] != 0) continue ;
location[vec[j][i].ss] = location[j] - vec[j][i].ff ;
stype[vec[j][i].ss] = 1 ;
for ( int k = 0 ; k < N ; ++k ) {
if ( location[k] != 0 ) continue ;
if ( stype[vec[k][0].ss] != 1 )
stype[k] = 2, location[k] = location[vec[k][0].ss] + vec[k][0].ff ;
}
}
/* location[0] = first ;
stype[0] = 1 ;
int c = -1 ;
for ( auto i:fromA ) {
if ( befA.count ( i.ss ) ) continue ;
// cout << i.ff << ' ' << i.ss << ' ' << c << endl ;
if ( c == -1 ) c = i.ss, location[c] = location[0] + i.ff, stype[c] = 2 ;
else {
int x = getDistance ( i.ss, c ) ;
cout << i.ss << ' ' << c << ' ' << dist[0][c] << ' ' << dist[0][i.ss] << ' ' << x << endl ;
if ( x == dist[0][i.ss] + dist[0][c] ) 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] + dist[j][c] == x ) c = i.ss, location[c] = location[j] - i.ff, stype[c] = 1 ;
else location[i.ss] = location[c] + x, stype[i.ss] = 2 ;
}
}*/
// for ( int i = 0 ; i < N ; ++i ) cout << location[i] << ' ' << stype[i] << endl ;
return ;
}
