#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
const int mxn = 5000, inf = 1e9;
int dist[4][mxn];
bool comp(int i, int j){
return dist[0][i] < dist[0][j];
}
void findLocation(int N, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
if(N==1) return;
int piv1 = 1;
for(int i = 1; i < N; i++){
dist[0][i] = getDistance(0,i);
if(dist[0][i] < dist[0][piv1])
piv1 = i;
}
location[piv1] = location[0] + dist[0][piv1];
stype[piv1] = 2;
for(int i = 1; i < N; i++) if(i!=piv1)
dist[1][i] = getDistance(piv1,i);
vector<int> comp1,comp2;
for(int i = 1; i < N; i++) if(i!=piv1){
if(dist[1][i]+dist[0][piv1]==dist[0][i])
comp1.push_back(i);
else
comp2.push_back(i);
}
sort(comp1.begin(),comp1.end(),comp);
sort(comp2.begin(),comp2.end(),comp);
if(!comp1.empty()){
int piv = comp1[0];
location[piv] = location[piv1] - dist[1][piv];
stype[piv] = 1;
set<pii> st; st.insert({location[piv],piv});
st.insert({location[0],0});
for(int i = 1; i < comp1.size(); i++){
int v = comp1[i];
int a = location[piv1] - dist[1][v];
auto it = st.lower_bound(make_pair(a+1,-1));
int cap = st.begin()->second;
int req = getDistance(cap,v);
int smt = 0;
while(next(it) != st.end()){
int u = it->second;
if(2*(it->first) - next(it)->first >= a){
it++; continue;
}
if(req - (location[u]-location[cap]) + dist[1][u] == dist[1][v]){
location[v] = -a + 2*location[u];
stype[v] = 2; smt = 1;
break;
}
it++;
}
if(smt==0){
location[v] = a;
stype[v] = 1;
st.insert({a,v});
}
}
}
if(!comp2.empty()){
int piv = comp2[0];
location[piv] = location[0] + dist[0][piv];
stype[piv] = 2;
set<pii> st; st.insert({location[piv],piv});
st.insert({location[piv1],piv1});
for(int i = 1; i < comp2.size(); i++){
int v = comp2[i];
int a = location[0] + dist[0][v];
auto it = st.lower_bound(make_pair(a,-1));
int cap = prev(st.end())->second;
int req = getDistance(v,cap);
int smt = 0;
while(prev(it) != st.begin()){
it--;
if(2*(it->first) - prev(it)->first <= a) continue;
int u = it->second;
if(req - (location[cap]-location[u]) + dist[0][u] == dist[0][v]){
location[v] = -a + 2*location[u];
stype[v] = 1; smt = 1; break;
}
}
if(smt==0){
location[v] = a;
stype[v] = 2;
st.insert({a,v});
}
}
}
}
