#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
map<ii, int> M;
int dist(int a, int b) {
if(a > b) swap(a, b);
if(M.count({a, b}))
return M[{a, b}];
return M[{a, b}] = getDistance(a, b);
}
void findLocation(int N, int first, int location[], int stype[]) {
for(int i = 0 ; i < N ; i++)
stype[i] = location[i] = 0;
stype[0] = 1;
location[0] = first;
int b = 1;
for(int i = 2 ; i < N ; i++)
if(dist(0, i) < dist(0, b))
b = i;
stype[b] = 2;
location[b] = location[0] + dist(0, b);
vector<int> lst;
lst.push_back(b);
int fst = 0;
vector<ii> cand;
for(int i = 0 ; i < N ; i++) {
if(i == 0 || i == b)
continue;
int d0 = dist(0, i);
int db = dist(b, i);
int d = dist(0, b);
if(d0 - db == d) {
if(db < d)
cand.push_back({d0, i});
} else
cand.push_back({d0, i});
}
sort(cand.begin(), cand.end());
for(auto p : cand) {
int d = dist(0, lst.back());
int w = p.Y;
int dlst = dist(lst.back(), w);
bool ins = true;
if(dlst >= d)
ins = false;
else {
int ind = 0;
while(dist(lst[ind], 0) < d - dlst)
ind++;
if(dist(lst[ind], 0) == d - dlst)
ins = false;
else {
if(dist(0, lst[ind]) + (dist(0, lst[ind]) + dlst - d) != dist(0, w))
ins = false;
}
}
if(ins) {
stype[w] = 1;
location[w] = location[lst.back()] - dlst;
} else {
stype[w] = 2;
location[w] = location[0] + dist(0, w);
lst.push_back(w);
}
}
int a = 0;
for(int i = 1 ; i < N ; i++)
if(i != b)
if(dist(b, i) < dist(b, a))
a = i;
stype[a] = 1;
location[a] = location[b] - dist(b, a);
fst = b;
lst.clear();
lst.push_back(a);
cand.clear();
for(int i = 0 ; i < N ; i++) {
if(stype[i])
continue;
cand.push_back({dist(fst, i), i});
}
sort(cand.begin(), cand.end());
for(auto p : cand) {
int d = dist(fst, lst.back());
int w = p.Y;
int dlst = dist(lst.back(), w);
bool ins = true;
if(dlst >= d)
ins = false;
else {
int ind = 0;
while(dist(lst[ind], fst) < d - dlst)
ind++;
if(dist(lst[ind], fst) == d - dlst)
ins = false;
else {
if(dist(fst, lst[ind]) + (dist(fst, lst[ind]) + dlst - d) != dist(fst, w))
ins = false;
}
}
if(ins) {
stype[w] = 2;
location[w] = location[lst.back()] + dlst;
} else {
stype[w] = 1;
location[w] = location[fst] - dist(fst, w);
lst.push_back(w);
}
}
//~ for(int i = 0 ; i < N ; i++)
//~ cout << stype[i] << " " << location[i] << endl;
//~ cout << endl;
}
