#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"
#ifdef tolbi
#include "geodeb.h"
#endif
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];
}
#ifdef tolbi
void cizl(int x){
GD_SEGMENT(x,0,x,1000);
GD_SEGMENT(x,0,x+500,-500);
GD_SEGMENT(x,1000,x+500,1500);
}
void cizr(int x){
GD_SEGMENT(x,0,x,1000);
GD_SEGMENT(x,0,x-500,-500);
GD_SEGMENT(x,1000,x-500,1500);
}
#else
void cizl(int x){
//ahmet23 pretty orz!...
}
void cizr(int x){
//ahmet23 pretty orz!...
}
#endif
void findLocation(int n, int __first, int pl[], int type[])
{
#ifdef tolbi
GD_INIT("out.html");
#endif
set<int> loc;
for (int i = 0; i < 5000; ++i)
{
for (int j = 0; j < 5000; j++){
dst[i][j]=-1;
}
}
for (int i = 0; i < n; ++i)
{
type[i]=-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;
map<int,int> mp;
cizl(pl[0]);
cizr(pl[ri]);
for (int i = 1; i < v.size(); i++){
int k = v[i];
if (dist(ri,k)+dist(ri,0)==dist(k,0)){
type[k]=1;
pl[k]=pl[ri]-dist(ri,k);
cizl(pl[k]);
if (pl[k]<pl[le]) le=k;
}
}
v.clear();
for (int i = 0; i < n; i++){
if (type[i]==1) loc.insert(pl[i]),mp[pl[i]]=i;
if (type[i]!=-1) continue;
v.push_back(i);
}
sort(v.begin(), v.end(), [&](int a, int b){
return dist(le,a)>dist(le,b);
});
int hri = ri;
for (int i = 0; i < v.size(); i++){
int k = v[i];
int ppos = dist(le,k)+pl[le];
auto it = loc.lower_bound(min(ppos,pl[ri]));
it--;
int eny = mp[*it];
if (dist(ri,k)==dist(eny,ri)+dist(eny,k)){
type[k]=2;
pl[k]=ppos;
}
else {
type[k]=1;
pl[k]=pl[hri]-dist(hri,k);
}
if (type[k]==2){
cizr(pl[k]);
}
}
}
