#pragma GCC optimize("Ofast")
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dist[5005][5005];
int get(int i, int j) {
if(dist[i][j] != 0) return dist[i][j];
return dist[i][j] = dist[j][i] = getDistance(i, j);
}
vector<int> xIsClosest[5005];
int negLoc[5005];
int vis[5005];
void findLocation(signed N, signed first, signed location[], signed stype[]) {
for(int i = 0; i < N; i++)
for(int j = 0; j < i; j++)
get(i, j);
vector<pair<int, int>> z;
for(int i = 0; i < N; i++) {
z.clear();
for(int j = 0; j < N; j++) {
if(i==j) continue;
z.push_back({get(i,j), j});
}
sort(z.begin(), z.end());
xIsClosest[z[0].second].push_back(i);
xIsClosest[i].push_back(z[0].second);
// cerr << i << "->" << z[0].second << endl;
}
z.clear();
for(int j = 1; j < N; j++) {
z.push_back({get(0,j), j});
}
sort(z.rbegin(), z.rend());
queue<pair<int, int>> q;
int xi = 1;
for(int i = 2; i < N; i++)
if(get(0,i) < get(0, xi))
xi = i;
memset(negLoc, -1, sizeof(negLoc));
negLoc[0]=first;
q.push({0, 1});
while(!q.empty()) {
int i = q.front().first;
int t = q.front().second;
vis[i]=1;
stype[i] = t;
// cerr << i << ": " << t << " " << negLoc[i] << endl;
q.pop();
for(auto j: xIsClosest[i]) {
if(vis[j]) continue;
vis[j]=1;
negLoc[j] = negLoc[i] + (t==1?get(i,j):-get(i,j));
q.push({j, t+(t==1)-(t==2)});
}
}
while(!z.empty()) {
int x = z.back().second;
z.pop_back();
if(vis[x]) continue;
if(get(x, 0) < get(x, xi)) {
q.push({x, 2});
negLoc[x] = negLoc[0] + get(x, 0);
} else {
q.push({x, 1});
negLoc[x] = negLoc[xi] - get(x, xi);
}
// cerr << endl;
while(!q.empty()) {
int i = q.front().first;
int t = q.front().second;
vis[i]=1;
stype[i] = t;
// cerr << i << ": " << t << " " << negLoc[i] << endl;
q.pop();
for(auto j: xIsClosest[i]) {
if(vis[j]) continue;
negLoc[j] = negLoc[i] + (t==1?get(i,j):-get(i,j));
q.push({j, t+(t==1)-(t==2)});
}
}
}
for(int i = 0; i < N; i++) {
if(negLoc[i] == -1) exit(-1);
if(!vis[i]) exit(-1);
location[i] = negLoc[i];
}
}
