#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> ostream& operator<<(ostream& os, vector<X> v){for (auto &it : v) os<<it<<" ";return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for (auto &it : v) os<<it<<" ";return os;}
ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for(auto &it : x) cin>>it;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1ll<<((int)(bi)))
typedef long long ll;
const ll INF = LONG_LONG_MAX;
const ll MOD = 1e9+9;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "rail.h"
int dst[5000][5000];
int dist(int a, int b){
if (a==b){
return dst[a][b]=0;
}
if (dst[a][b]==-1){
dst[a][b]=dst[b][a]=getDistance(a,b);
}
return dst[a][b];
}
void findLocation(int n, int __first, int pl[], int type[])
{
for (int i = 0; i < 5000; ++i)
{
for (int j = 0; j < 5000; j++){
dst[i][j]=-1;
}
}
pl[0]=__first;
type[0]=1;
vector<int> v(n-1);
iota(v.begin(), v.end(), 1);
sort(v.begin(), v.end(), [&](int a, int b){
return dist(0,a)<dist(0,b);
});
pl[v[0]]=pl[0]+dist(0,v[0]);
type[v[0]]=2;
int le = 0;
int ri = v[0];
int stage = 1;
for (int i = 1; i < v.size(); i++){
int k = v[i];
if (stage==1){
if (dist(le,k)>dist(ri,k)){
stage=2;
}
else {
pl[k]=pl[le]+dist(le,k);
type[k]=2;
}
}
if (stage==2){
if (pl[ri]-dist(ri,k)<pl[le]){
stage=3;
}
else {
pl[k]=pl[ri]-dist(ri,k);
type[k]=1;
}
}
if (stage==3){
if (dist(le,k)<dist(ri,k)){
stage=4;
}
else {
pl[k]=pl[ri]-dist(ri,k);
type[k]=1;
}
}
if (stage==4){
pl[k]=pl[le]+dist(le,k);
type[k]=2;
}
if (type[k]==1){
if (pl[k]<pl[le]) le=k;
}
else {
if (pl[k]>pl[ri]) ri=k;
}
}
}
