#include <bits/stdc++.h>
#include "rail.h"
//~ #include "grader.cpp"
using namespace std;
const int N = 5001;
int n, dist[N][N];
vector <int> loc, type;
int ask(int x, int y){
if(y < x) swap(x, y);
if(dist[x][y] == -1) dist[x][y] = getDistance(x, y);
return dist[x][y];
}
void solvel(vector <int> l, int d){
set <int> all(l.begin(), l.end());
while(all.size()){
int C = -1;
for(auto &i : all){
if(C == -1 || ask(i, d) < ask(C, d)){
C = i;
}
}
type[C] = 1;
loc[C] = loc[d] - ask(C, d);
all.erase(C);
int D = -1;
for(auto &i : all){
if(D == -1 || ask(i, C) < ask(D, C)){
D = i;
}
}
if(D == -1 || ask(C, D) >= ask(C, d)){
continue;
}
type[D] = 2;
loc[D] = loc[C] + ask(D, C);
all.erase(D);
vector <int> to_remove;
for(auto &i : all){
if(ask(C, i) < ask(D, i)){
type[i] = 2;
loc[i] = loc[C] + ask(i, C);
to_remove.push_back(i);
}
}
for(auto &i : to_remove){
all.erase(i);
}
}
}
void solver(vector <int> r, int c){
set <int> all(r.begin(), r.end());
while(all.size()){
int D = -1;
for(auto &i : all){
if(D == -1 || ask(i, c) < ask(D, c)){
D = i;
}
}
type[D] = 2;
loc[D] = loc[c] + ask(c, D);
all.erase(D);
int C = -1;
for(auto &i : all){
if(C == -1 || ask(i, D) < ask(C, D)){
C = i;
}
}
if(C == -1 || ask(C, D) >= ask(c, D)){
continue;
}
type[C] = 1;
loc[C] = loc[D] - ask(C, D);
all.erase(C);
vector <int> to_remove;
for(auto &i : all){
if(ask(i, D) < ask(i, C)){
type[i] = 1;
loc[i] = loc[D] - ask(i, D);
to_remove.push_back(i);
}
}
for(auto &i : to_remove){
all.erase(i);
}
}
}
void findLocation(int N, int first, int location[], int stype[]){
n = N;
loc.assign(n, 0);
type.assign(n, 0);
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
dist[i][j] = -1;
}
}
loc[0] = first;
type[0] = 1;
int d = -1;
for(int i = 1 ; i < n ; i++){
if(d == -1 || ask(0, i) < ask(0, d)){
d = i;
}
}
type[d] = 2;
loc[d] = loc[0] + ask(0, d);
int c = -1;
for(int i = 0 ; i < n ; i++){
if(i == d) continue;
if(c == -1 || ask(i, d) < ask(c, d)){
c = i;
}
}
type[c] = 1;
loc[c] = loc[d] - ask(c, d);
vector <int> l, r;
for(int i = 0 ; i < n ; i++){
if(i == c || i == d) continue;
if(ask(d, i) < ask(c, i)) l.push_back(i);
else r.push_back(i);
}
solvel(l, d);
solver(r, c);
for(int i = 0 ; i < n ; i++){
location[i] = loc[i];
stype[i] = type[i];
}
}
